ON THE CIRCUIT-SIZE OF INVERSES
Autor: | Jean-Camille Birget |
---|---|
Rok vydání: | 2011 |
Předmět: |
FOS: Computer and information sciences
Discrete mathematics Computational complexity theory Existential quantification Inverse Function (mathematics) One-way function Computational Complexity (cs.CC) Surjective function Computer Science - Computational Complexity Computer Science (miscellaneous) Time complexity Electronic circuit Mathematics |
Zdroj: | International Journal of Foundations of Computer Science. 22:1925-1938 |
ISSN: | 1793-6373 0129-0541 |
DOI: | 10.1142/s0129054111009124 |
Popis: | We reprove a result of Boppana and Lagarias: If Pi_2^P is different from Sigma_2^P then there exists a partial function f that is computable by a polynomial-size family of circuits, but no inverse of f is computable by a polynomial-size family of circuits. We strengthen this result by showing that there exist length-preserving total functions that are one-way by circuit size and that are computable in uniform polynomial time. We also prove, if Pi_2^P is different from Sigma_2^P, that there exist polynomially balanced total surjective functions that are one-way by circuit size; here non-uniformity is used. Comment: 8 pages |
Databáze: | OpenAIRE |
Externí odkaz: |