13
$\begingroup$

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}$?

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

2 Answers 2

4
$\begingroup$

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.

References

[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.

$\endgroup$
5
  • $\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
    Commented Feb 1, 2013 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
    Commented Feb 1, 2013 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$ Commented Feb 1, 2013 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
    Commented Feb 1, 2013 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$ Commented Feb 1, 2013 at 21:43
5
$\begingroup$

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$.

$\endgroup$
5
  • $\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
    Commented Jan 19, 2013 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
    Commented Jan 20, 2013 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
    Commented Jan 20, 2013 at 20:02
  • $\begingroup$ Yes, perfectly. $\endgroup$
    – domotorp
    Commented Jan 21, 2013 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
    Commented Jan 26, 2013 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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