Easy sets and hard certificate schemes

DOI10.1007/S002360050109MaRDI QIDQ1374784zbMATH OpenOpenAlexFDO

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

Publication date 10 December 1997

Published in Acta Informatica (Search for Journal in Brave)

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

zbMATH Keywords

accepting pathsKolmogorov complexityNP certificate schemes

Mathematics Subject Classification ID

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

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.

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

Cited in

(13)

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

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)