It easy to see that if $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$ then there are total $\mathsf{NP}$ search problems which cannot be solved in polynomial time (create a total search problem by having both the witnesses for membership and the witnesses for nonmembership).

Is the converse also true, i.e.

Does existence of a total $\mathsf{NP}$ search problem not solvable in polynomial time imply $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$?

  • $\begingroup$ Do you mean a total search problem with NP decision problem? Is integer factorization such problem? $\endgroup$ – Mohammad Al-Turkistany Jan 19 '13 at 12:24
  • 2
    $\begingroup$ I think he means TFNP. $\endgroup$ – domotorp Jan 19 '13 at 14:35

I assume that P, NP, and coNP in the question are classes of languages, not classes of promise problems. I use the same convention in this answer. (Just in case, if you are talking about classes of promise problems, then the answer is affirmative because P = NP∩coNP as classes of promise problems is equivalent to P = NP.)

Then the answer is negative in a relativized world.

The statement TFNP ⊆ FP is known as Proposition Q in the literature [FFNR03]. There is a weaker statement called Proposition Q’ [FFNR03] that every total NPMV relation with one-bit answers is in FP. (Here a relation with one-bit answers means a subset of {0,1}*×{0,1}.) It is easy to see that Proposition Q relative to some oracle implies Proposition Q’ relative to the same oracle.

Fortnow and Rogers [FR02] considered the relationships between the statement P = NP∩coNP, Proposition Q’, and a few other related statements in relativized worlds. In particular, Theorem 3.2 (or Theorem 3.3) in [FR02] implies that there is an oracle relative to which P = NP∩coNP but Proposition Q’ does not hold (and therefore Proposition Q does not hold, either). Therefore, in a relativized world, P = NP∩coNP does not imply Proposition Q; or by taking contrapositive, existence of TFNP relation which cannot be computed in polynomial time does not imply P ≠ NP∩coNP.


[FFNR03] Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, and John D. Rogers. Inverting onto functions. Information and Computation, 186(1):90–103, Oct. 2003. DOI: 10.1016/S0890-5401(03)00119-6.

[FR02] Lance Fortnow and John D. Rogers. Separability and one-way functions. Computational Complexity, 11(3–4):137–157, June 2002. DOI: 10.1007/s00037-002-0173-4.

  • $\begingroup$ Thanks Tsuyoshi. There is also a result in type two version of the problem which shows the answer is provably negative there: Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi, "The Relative Complexity of NP Search Problems", 1998 $\endgroup$ – Kaveh Feb 1 '13 at 17:56
  • $\begingroup$ By the way, is there any known argument for them not being equivalent in the non-relativized world (based on some conjecture in complexity theory or cryptography)? I feel that we should be able to say something based on the following collision finding problem which is in TFNP but seems strange if was possible to reduce it (even with randomized reductions) to a TFUP problem: given a circuit $C:2^{n+1}\to2^n$, find a collision in $C$. $\endgroup$ – Kaveh Feb 1 '13 at 17:57
  • $\begingroup$ @Kaveh: I am not sure if I understand your question in the comment. In the non-relativized world, the only way to say that “P=NP∩coNP” and “TFNP⊆FP” are not equivalent is to show that the former holds and that the latter does not hold, unless we prove some logical independence result. But the popular belief is that P≠NP∩coNP, which implies that “P=NP∩coNP” and “TFNP⊆FP” are equivalent (because both are false). Therefore, I do not know what kind of conjecture you are looking for. $\endgroup$ – Tsuyoshi Ito Feb 1 '13 at 20:30
  • $\begingroup$ I don't know if it makes sense, but I was thinking of something like the following: the search problem of finding collisions in a circuit with n+1 inputs and n outputs is in $\mathsf{TFNP}$, however if SPRNG exists its corresponding decision problem (witness extension) is not in $\mathsf{P^{NP\cap coNP}}$. $\endgroup$ – Kaveh Feb 1 '13 at 21:24
  • $\begingroup$ @Kaveh: Are you talking about inequivalence between two propositions “P=NP∩coNP” and “TFNP⊆FP,” or inequivalence between something else? $\endgroup$ – Tsuyoshi Ito Feb 1 '13 at 21:43

For total UP the answer is yes, because the question "Is the i'th bit of the solution 1?" is in $NP \cap co-NP$.

  • $\begingroup$ So $$\mathsf{TFUP} \neq \mathsf{FP}\implies \mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P} \implies \mathsf{TFNP} \neq \mathsf{FP}$$ but we don't know if $$\mathsf{TFNP} \neq \mathsf{FP} \implies \mathsf{TFUP} \neq \mathsf{FP}$$? $\endgroup$ – Kaveh Jan 19 '13 at 22:55
  • $\begingroup$ I cannot say that WE don't know, but I certainly don't. Of course if we allow randomized reductions, then you can do the Valiant-Vazirani trick and the last implication also becomes true. (Unless I am wrong...) $\endgroup$ – domotorp Jan 20 '13 at 19:48
  • $\begingroup$ Randomized reduction will not give $\mathsf{FP}$, it will give a randomized algorithm (i.e. if we have a polytime algorithms for $\mathsf{TFUP}$ then we have randomized polynomial time algorithms for $\mathsf{TFNP}$). However since we conjecture that the randomized polytime classes are the the same as $\mathsf{FP}$ then that would imply that the reverse should also hold. Do I understand correctly? $\endgroup$ – Kaveh Jan 20 '13 at 20:02
  • $\begingroup$ Yes, perfectly. $\endgroup$ – domotorp Jan 21 '13 at 8:09
  • $\begingroup$ It seems that the Valiant-Vazirani doesn't work here (or at least I don't see how it works). The problem is that the result is a promise problem, e.g. SAT to USAT. We need a non-promise problem. And there seems to be reasons to believe that these two should not be equal. I will post a new question about TFNP and TFUP. $\endgroup$ – Kaveh Jan 26 '13 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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