The Complexity of Decision Versus Search
- 1 February 1994
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 23 (1), 97-119
- https://doi.org/10.1137/s0097539792228289
Abstract
No abstract availableThis publication has 13 references indexed in Scilit:
- Languages that are easier than their proofsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On the theory of average case complexityJournal of Computer and System Sciences, 1992
- Limitations of the upward separation techniqueTheory of Computing Systems, 1991
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systemsJournal of the ACM, 1991
- Non-deterministic exponential time has two-prover interactive protocolscomputational complexity, 1991
- The Knowledge Complexity of Interactive Proof SystemsSIAM Journal on Computing, 1989
- Complexity classes without machines: On complete languages for UPTheoretical Computer Science, 1988
- The complexity of parallel searchJournal of Computer and System Sciences, 1988
- Sparse sets in NP-P: EXPTIME versus NEXPTIMEInformation and Control, 1985
- The complexity of promise problems with applications to public-key cryptographyInformation and Control, 1984