On being incoherent without being very hard

DOI10.1007/BF01276436zbMath0752.68038MaRDI QIDQ1198954

Joan Feigenbaum, Richard Beigel

Publication date: 16 January 1993

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

incoherenceautoreducibilityprogram checkabilityrandom-self- reducibility

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (10)

Autoreducibility and mitoticity of logspace-complete sets for NP and other classes ⋮ Autoreducibility, mitoticity, and immunity ⋮ Introduction to Autoreducibility and Mitoticity ⋮ Autoreducibility of NP-complete sets under strong hypotheses ⋮ Collapsing and separating completeness notions under average-case and worst-case hypotheses ⋮ On the autoreducibility of functions ⋮ Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions ⋮ From Logic to Theoretical Computer Science – An Update ⋮ Non-mitotic Sets ⋮ Non-mitotic sets

Cites Work

• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• Robust algorithms: a different approach to oracles
• On helping by robust oracle machines
• On hiding information from an oracle
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• The Knowledge Complexity of Interactive Proof Systems
• Relativization of the Theory of Computational Complexity
• Tally languages and complexity classes

This page was built for publication: On being incoherent without being very hard