Languages that are easier than their proofs
- 9 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Languages in NP are presented for which it is harder to prove membership interactively than it is to decide this membership. Similarly, languages where checking is harder than computing membership are presented. Under assumptions about triple-exponential time, incoherent sets in NP are constructed. Without any assumptions, incoherent sets are constructed in DSPACE (n to the log n), yielding the first uncheckable and non-random-self-reducible sets in that space.Keywords
This publication has 19 references indexed in Scilit:
- On the random-self-reducibility of complete setsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Lower bounds on random-self-reducibilityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A characterization of Hash P by arithmetic straight line programsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- IP = PSPACEJournal of the ACM, 1992
- Coherent functions and program checkersPublished by Association for Computing Machinery (ACM) ,1990
- The Knowledge Complexity of Interactive Proof SystemsSIAM Journal on Computing, 1989
- Designing programs that check their workPublished by Association for Computing Machinery (ACM) ,1989
- Multi-prover interactive proofs: how to remove intractabilityPublished by Association for Computing Machinery (ACM) ,1988
- Sparse sets in NP-P: EXPTIME versus NEXPTIMEInformation and Control, 1985
- A Note on Sparse Complete SetsSIAM Journal on Computing, 1979