A characterization of Hash P by arithmetic straight line programs
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Hash P functions are characterized by certain straight-line programs of multivariate polynomials. The power of this characterization is illustrated by a number of consequences. These include a somewhat simplified proof of S. Toda's (1989) theorem that PH contained in P/sup Hash P/, as well as an infinite class of potentially inequivalent checkable functions.Keywords
This publication has 9 references indexed in Scilit:
- Algebraic methods for interactive proof systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Non-deterministic exponential time has two-prover interactive protocolscomputational complexity, 1992
- IP = PSPACEJournal of the ACM, 1992
- The Knowledge Complexity of Interactive Proof SystemsSIAM Journal on Computing, 1989
- Designing programs that check their workPublished by Association for Computing Machinery (ACM) ,1989
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classesJournal of Computer and System Sciences, 1988
- Proofs that yield nothing but their validity and a methodology of cryptographic protocol designPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- NP is as easy as detecting unique solutionsTheoretical Computer Science, 1986
- AlternationJournal of the ACM, 1981