Collapsing and Separating Completeness Notions Under Average-Case and Worst-Case Hypotheses

This paper presents the following results on sets that are complete for NP.

1. (i)

   If there is a problem in NP that requires \(2^{n^{\Omega(1)}}\) time at almost all lengths, then every many-one NP-complete set is complete under length-increasing reductions that are computed by polynomial-size circuits.

2. (ii)

   If there is a problem in co-NP that cannot be solved by polynomial-size nondeterministic circuits, then every many-one NP-complete set is complete under length-increasing reductions that are computed by polynomial-size circuits.

3. (iii)

   If there exist a one-way permutation that is secure against subexponential-size circuits and there is a hard tally language in NP∩co-NP, then there is a Turing complete language for NP that is not many-one complete.

Our first two results use worst-case hardness hypotheses whereas earlier work that showed similar results relied on average-case or almost-everywhere hardness assumptions. The use of average-case and worst-case hypotheses in the last result is unique as previous results obtaining the same consequence relied on almost-everywhere hardness results.

We thank anonymous reviewers for several comments and suggestions that led to a vastly improved presentation of the paper.

Authors and Affiliations

1. Linked In Corporation, Mountain View, USA

   Xiaoyang Gu

2. Department of Computer Science, University of Wyoming, Laramie, USA

   John M. Hitchcock

3. Department of Computer Science, Iowa State University, Ames, USA

   A. Pavan

Corresponding author

Correspondence to A. Pavan.

Preliminary version appeared at 27th International Symposium on Theoretical Aspects of Computer Science.

Part of the research of X.G. was done while the author was at Iowa State University. Research supported in part by NSF grants 0652569 and 0728806.

Research of J.M.H. supported in part by NSF grants 0515313 and 0652601 and by an NWO travel grant. Part of this research was done while this author was on sabbatical at CWI.

Research of A.P. supported in part by NSF grants 0830479 and 0916797.

Appendix

Here we provide a proof of Lemma 4.5

Definition

Let x,y∈{0,1}^m. \(\Delta(x,y) = \frac{1}{m}|\{ i \mid x[i]\neq y[i] \} |\). We say that E:{0,1}ⁿ→{0,1}^m is an error correcting code with distance δ if for every x≠y∈{0,1}ⁿ, Δ(E(x),E(y))≥δ.

Theorem 5.1

(Johnson Bound [27])

If E:{0,1}ⁿ→{0,1}^m is an ECC with distance at least \(\frac{1}{2}-\epsilon\), then for every x∈{0,1}^m, and \(\eta \geq \sqrt{\epsilon}\), there exist at most l≤1/(2η ²) strings y ₁,…,y _l ∈E({0,1}ⁿ) such that \(\Delta(x, y_{i})\leq \frac{1}{2}-\eta\) for every i∈[l].

Consider an ECC \(E:\{0,1\}^{2n\log n}\rightarrow\{0,1\}^{n^{4}}\) with distance 1/2−/2n. An explicit example of such ECC is the code obtained by concatenating the Walsh-Hadamard code with the Reed-Solomon code. We will view strings of length 2nlogn and n ⁴ truth tables of languages at certain lengths. For this, both 2nlogn and n ⁴ must be powers of 2. If n is of the form \(2^{2^{k-1}}\), then both 2nlogn and n ⁴ are powers of two.

For any language L″, let L′ be fold(L″). It is clear that L″∈NEEE∩coNEEE if and only if L′∈NEEE∩coNEEE. The following fact is easy to verify.

Lemma 5.2

If L″∉EEE/O(logn), then L′∉EEE/O(logn) and for every EEE/O(logn) algorithm \(\mathcal{A}\), there are infinitely many lengths n of the form 2^k+1+k such that \(\mathcal{A}\) fails to decide L′ correctly at length n.

Lemma 4.5

If there is a language in L″∈NEEE∩coNEEE−EEE/O(logn), then there is a language L∈NEEE∩coNEEE such that for every EEE/O(logn) algorithm \(\mathcal{A}\), there exist infinitely many n and \(\mathcal{A}\) correctly decides L on at most \(\frac{1}{2}+\frac{1}{n}\) fraction of strings from Σⁿ.

Proof

Let L″∈NEEE∩coNEEE−EEE/O(log). Let L′=fold(L″). Let L be the language such that for every k∈ℕ, \(L_{2^{k+1}} = E(L'_{2^{k-1}+k})\) where E is the WH-RS code. On other lengths, we set L to be empty. It is clear that L∈NEEE∩coNEEE since we can actually compute the truth table of L′ in NEEE∩coNEEE.

Now, for the sake of contradiction, assume that there is an EEE/O(logn) algorithm \(\mathcal{A}\) that correctly decides L on more than \(\frac{1}{2}+\frac{1}{n}\) fraction of inputs at every length n. We will first show that this yields a EEE/O(logn) algorithm for L. Since L is empty at lengths that are not of the form 2^k+1, we can decide L easily at those lengths. Thus we will concentrate on lengths of the form 2^k+1.

Consider n of the form 2^k+1. By the definition of L, we know that \(L_{n} = E(L'_{2^{k-1}+k})\). Let N=2ⁿ. Recall that the distance of the code E is \(\frac{1}{2}-\epsilon\), where \(\epsilon= \frac{1}{2\sqrt[4]{N}}\). Let \(\eta= \frac{1}{n}=\frac{1}{\log N}> \sqrt{\epsilon}\).

By running \(\mathcal{A}\) on all strings of length n compute a candidate sequence, x∈{0,1}^N, for L _n . By our assumption, A is correct on at least \(\frac{1}{2}+\frac{1}{n}\) of strings from Σⁿ. Thus \(\Delta(x, L_{n}) \leq\frac{1}{2}-\frac{1}{n}\). By the Johnson bound 5.1, there exist at most \(l \leq \frac{n^{2}}{2}\) strings y ₁,…,y _l in \(E(\Sigma^{2^{k-1}+k})\) such that \(\Delta(x, y_{i}) \leq\frac{1}{2}-\frac{1}{n}\). By running E on all strings from \(\Sigma^{2^{k-1}+k}\), we can compute these y _i s. Since WH-RS code is computable in polynomial time, this computation can be done in triple exponential time. Since \(L_{n} =E(L'_{2^{k-1}+k})\), there exists a j, 1≤j≤l such that L _n =y _j . Thus logl=O(logn) bits of information is enough to identify j for which L _n =y _j . Thus L∈EEE/O(logn).

Recall that \(L_{n} = E(L'_{2^{k-1}+k}\)) when n=2^k. Since L∈EEE/O(logn), by inverting the WH-RS code E, we can decide L′ correctly on all lengths of the form 2^k+1+k, using an EEE/O(logn) algorithm. This contradicts Lemma 5.2. □

Reprints and permissions