Easy sets and hard certificate schemes

DOI10.1007/S002360050109zbMATH Open0883.68072arXivcs/9907035OpenAlexW1697825390MaRDI QIDQ1374784FDOQ1374784

Authors: Jörg Rothe, Gerd Wechsung, Lane A. Hemaspaandra 

Publication date: 10 December 1997

Published in: Acta Informatica (Search for Journal in Brave)

Abstract: Can easy sets only have easy certificate schemes? In this paper, we study the class of sets that, for all NP certificate schemes (i.e., NP machines), always have easy acceptance certificates (i.e., accepting paths) that can be computed in polynomial time. We also study the class of sets that, for all NP certificate schemes, infinitely often have easy acceptance certificates. In particular, we provide equivalent characterizations of these classes in terms of relative generalized Kolmogorov complexity, showing that they are robust. We also provide structural conditions---regarding immunity and class collapses---that put upper and lower bounds on the sizes of these two classes. Finally, we provide negative results showing that some of our positive claims are optimal with regard to being relativizable. Our negative results are proven using a novel observation: we show that the classical ``wide spacing oracle construction technique yields instant non-bi-immunity results. Furthermore, we establish a result that improves upon Baker, Gill, and Solovay's classical result that NP eq P = NP cap coNP holds in some relativized world.

Full work available at URL: https://arxiv.org/abs/cs/9907035

Recommendations

• Immunity, simplicity, probabilistic complexity classes and relativizations
• scientific article; zbMATH DE number 4011940
• Relativizing relativized computations
• Sparse Sets in : Relativizations
• Immunity and simplicity in relativizations of probabilistic complexity classes

zbMATH Keywords

Kolmogorov complexityaccepting pathsNP certificate schemes

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cited In (13)

• Comparing reductions to NP-complete sets
• One-way permutations and self-witnessing languages
• Tally NP sets and easy census functions.
• Closure and nonclosure properties of the classes of compressible and rankable sets
• A Downward Collapse within the Polynomial Hierarchy
• The opacity of backbones
• Reducing the number of solutions of NP functions
• Inverting onto functions.
• Immunity and Simplicity for Exact Counting and Other Counting Classes
• Recursion-theoretic ranking and compression
• Characterizations and existence of easy sets without hard subsets
• Characterizing the existence of one-way permutations
• On characterizing the existence of partial one-way permutations

This page was built for publication: Easy sets and hard certificate schemes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1374784)