ON THE CIRCUIT-SIZE OF INVERSES

Autor: Jean-Camille Birget
Rok vydání: 2011
Předmět:
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