__
TR10-034 | 7th March 2010 20:47
__

#### The Program-Enumeration Bottleneck in Average-Case Complexity Theory

**Abstract:**
Three fundamental results of Levin involve algorithms or reductions

whose running time is exponential in the length of certain programs. We study the

question of whether such dependency can be made polynomial.

(1) Levin's ``optimal search algorithm'' performs at most a constant factor more slowly

than any other fixed algorithm. The constant, however, is exponential in the length

of the competing algorithm.

We note that the running time of a universal search cannot be made ``fully

polynomial'' (that is, the relation between slowdown and program length cannot

be made polynomial), unless P=NP.

(2) Levin's ``universal one-way function'' result has the following structure:

there is a polynomial time computable function $f_{Levin}$ such that if there is

a polynomial time computable adversary $A$ that inverts $f_{Levin}$ on an inverse

polynomial fraction of inputs, then for every polynomial time computable function $g$

there also is a polynomial time adversary $A_g$ that inverts $g$ on an inverse

polynomial fraction of inputs. Unfortunately, again the running time of $A_g$ depends

exponentially on the bit length of the program that computes $g$ in polynomial time.

We show that

a fully polynomial uniform reduction from an arbitrary one-way

function to a specific one-way function is not possible relative to an oracle that

we construct, and so no ``universal one-way function'' can have a fully polynomial

security analysis via relativizing techniques.

(3) Levin's completeness result for distributional NP problems implies that if a specific

problem in NP is easy on average under the uniform distribution, then every language $L$

in NP is also easy on average under any polynomial time computable distribution. The

running time of the implied algorithm for $L$, however, depends exponentially on the

bit length of the non-deterministic polynomial time Turing machine that decides $L$.

We show that if a completeness result for distributional NP can be proved

via a ``fully uniform'' and ``fully polynomial'' time reduction, then there is a worst-case

to average-case reduction for NP-complete problems. In particular, this means

that a fully polynomial completeness result for distributional NP is impossible,

even via randomized truth-table reductions, unless the polynomial hierarchy collapses.