A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly

DOI10.1016/0022-0000(93)90008-KzbMath0771.68051OpenAlexW2077499967MaRDI QIDQ2366689

Yanyan Li

Publication date: 18 August 1993

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(93)90008-k

zbMATH Keywords

structural complexitymeasures of polynomial time behavior in sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Fixed-parameter decidability: Extending parameterized complexity analysis, Bi-immunity results for cheatable sets, Strong self-reducibility precludes strong immunity, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Bi-immunity results for cheatable sets
• On self-reducibility and weak P-selectivity
• On helping by robust oracle machines
• Polynomial terse sets
• Reductions on NP and p-selective sets
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Bounded queries to SAT and the Boolean hierarchy
• Terse, superterse, and verbose sets
• Self-reducibility
• The polynomial-time hierarchy and sparse oracles
• A Note on Sparse Complete Sets
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
• Semirecursive Sets and Positive Reducibility