Arithmetization: A new method in structural complexity theory
- 1 March 1991
- journal article
- research article
- Published by Springer Nature in computational complexity
- Vol. 1 (1), 41-66
- https://doi.org/10.1007/bf01200057
Abstract
No abstract availableKeywords
This publication has 20 references indexed in Scilit:
- Non-deterministic exponential time has two-prover interactive protocolscomputational complexity, 1991
- #P-COMPLETENESS VIA MANY-ONE REDUCTIONSInternational Journal of Foundations of Computer Science, 1991
- Hiding instances in multioracle queriesLecture Notes in Computer Science, 1990
- The Knowledge Complexity of Interactive Proof SystemsSIAM Journal on Computing, 1989
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classesJournal of Computer and System Sciences, 1988
- Circuit definitions of nondeterministic complexity classesLecture Notes in Computer Science, 1988
- NP is as easy as detecting unique solutionsTheoretical Computer Science, 1986
- AlternationJournal of the ACM, 1981
- The complexity of computing the permanentTheoretical Computer Science, 1979
- The polynomial-time hierarchyTheoretical Computer Science, 1976