Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Are there any known barriers to show the following invariant (perhaps by some sort of induction)?

Let $\Sigma$ be some finite alphabet with $|\Sigma| \geq 2$, let $M$ be some (deciding) deterministic Turing machine with input alphabet $\Sigma$, and let $L_0 \subseteq \Sigma^{\star}$ be some non-sparse, $\mbox{NP}$-complete language.
Then at least one of the following properties hold:

  1. $M$ doesn't terminate always.
  2. $M$ has superpolynomial time complexity.
  3. $L(M) \triangle L_0$ is non-sparse.

Concise problem description: $\mbox{NP} \not\subseteq \mbox{P-close}$ (according to Tsuyoshi Ito, see his answer).

Caution: This problem is equivalent to $\mbox{P} \neq \mbox{NP}$.

share|cite|improve this question
If this is a research-level question, you can try asking it at CSTheory. –  M.S. Dousti Feb 26 '11 at 14:15
I am no researcher and therefore I am only privately interested in this question. –  Steffen Schuler Feb 26 '11 at 15:47
1) You don't have to be a researcher to ask research-level questions. 2) If you know that the problem is equivalent to P vs. NP, why bother asking it? –  Qiaochu Yuan Feb 26 '11 at 16:23
If your question is equivalent to "Does anyone know how to solve P $\neq$ NP?", then the answer is certainly "no". If you cross-post this question to CSTheory, it may not be well-received. If you re-phrase your question to something like "Are there known barriers to this approach to P $\neq$ NP?", this might be better. However, you'll need to be much more explicit in your approach. –  mhum Feb 26 '11 at 16:35
@Steffen: You should first present a plan of attack for this particular theorem, in other words, an outline of a proof, and only then can we answer your question. –  Yuval Filmus Feb 26 '11 at 17:30

1 Answer 1

up vote 6 down vote accepted

This is a slightly more detailed version of some of my comments on your cross-posting on

The statement which you described can be concisely written as NP ⊈ P-close. Here P-close is the class of decision problems for which there exists a polynomial-time algorithm A such that the set of instances on which A fails to answer correctly is sparse.

It is easy to see that P ⊆ P-close ⊆ P/poly, from which it is easy to see the implications hold that NP ⊈ P/poly ⇒ NP ⊈ P-close ⇒ P≠NP. Since NP ⊈ P-close implies P≠NP, any proof of NP ⊈ P-close must also overcome the relativization barrier and the algebrization barrier. I do not know if the natural-proof barrier (which every proof of NP ⊈ P/poly must overcome) necessarily applies to NP ⊈ P-close.

I do not think that it is known that NP ⊈ P-close is equivalent to P≠NP as you claim.

Edit: On the contrary to what I wrote in an earlier revision, I learned that NP ⊈ P-close is indeed equivalent to P≠NP. Although I already answered your question about barriers above, I guess that writing down the proof of this equivalence may be useful. The proof is based on what you described on with one modification (namely, I use the result by Ogihara and Watanabe instead of Mahaney’s theorem).

As stated above, we have the implication NP ⊈ P-close ⇒ P≠NP. We will prove the converse: NP ⊆ P-close ⇒ P=NP.

A polynomial-time k-truth-table reduction from a language L1 to a language L2 is a Turing reduction from L1 to L2 which invokes the oracle at most k times nonadaptively. Note that a many-one reduction is a special case of a 1-truth-table reduction. Ogihara and Watanabe [OW91] proved the following result:

Theorem [OW91]. If some sparse language is NP-complete under polynomial-time k-truth-table reducibility for some constant k, then P=NP.

Note that this theorem generalizes Mahaney’s theorem, which is the special case of the theorem where the reduction is restricted to a polynomial-time many-one reduction.

Assume NP ⊆ P-close. Then SAT ∈ P-close. Equivalently, there exists a language L∈P such that the symmetric difference S=SAT△L is sparse. Then the following is a polynomial-time 1-truth-table reduction from SAT to S: given an input x, decide (in polynomial time) whether xL and decide (by invoking the oracle for S) whether xS, and return the XOR of the two results. Therefore, the sparse set S is NP-complete under polynomial-time 1-truth-table reducibility. This implies P=NP by the aforementioned theorem by Ogihara and Watanabe.

[OW91] Mitsunori Ogihara and Osamu Watanabe. On polynomial-time bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal on Computing, 20(3):471–483, June 1991.

share|cite|improve this answer
@Tsuyoshi: Thank you very much for your answer. –  Steffen Schuler Feb 27 '11 at 19:15
For the last statement of Tsuyoshi I humbly refer the community to the ongoing discussion in cstheory. –  Steffen Schuler Feb 27 '11 at 19:17
@Steffen: Perhaps you can edit the question to add your comments, in reference to Tsuyoshi's answer, rather than edit Tsuyoshi's answer directly. –  Arturo Magidin Feb 28 '11 at 0:30
@Arturo: All revisions to this answer so far were made by me, and “you” in the added part refers to Steffen. My apologies if it was not clear. –  Tsuyoshi Ito Feb 28 '11 at 0:33
@Steffen: (1) In the meanwhile, I learned that NP ⊈ P-close is indeed equivalent to P≠NP. See my updated answer. (2) I read your addendum to the question. I do not think that I followed everything, but I think that it fails because both $C$ and $\bar{C}$ can be satisfiable at the same time. –  Tsuyoshi Ito Feb 28 '11 at 1:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.