Title :
Languages that are easier than their proofs
Author :
Beigel, Richard ; Bellare, Mihir ; Feigenbaum, Joan ; Goldwasser, Shafi
Author_Institution :
Dept. of Comput. Sci., Yale Univ., New Haven, CT, USA
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 :
computational complexity; formal languages; DSPACE; NP; formal languages; incoherent sets; membership; nonrandom self-reducible sets; triple-exponential time; Computer science; NP-complete problem; Polynomials; Search problems;
Conference_Titel :
Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
Conference_Location :
San Juan
Print_ISBN :
0-8186-2445-0
DOI :
10.1109/SFCS.1991.185343
