On the circuit-size of inverses

Details On the circuit-size of inverses On the circuit-size of inverses

2009-12-18

arxiv.org/abs/0912.3730v2

Computer Science

Computational Complexity

8 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the circuit-size of inverses does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the circuit-size of inverses, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the circuit-size of inverses will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-350029