Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 13 down vote favorite
1

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

share|improve this question
Do you mean a total search problem with NP decision problem? Is integer factorization such problem? – Mohammad Al-Turkistany Jan 19 at 12:24
2  
I think he means TFNP. – domotorp Jan 19 at 14:35

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
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 – Kaveh♦ Feb 1 at 17:56
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$. – Kaveh♦ Feb 1 at 17:57
@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. – Tsuyoshi Ito Feb 1 at 20:30
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}}$. – Kaveh♦ Feb 1 at 21:24
@Kaveh: Are you talking about inequivalence between two propositions “P=NP∩coNP” and “TFNP⊆FP,” or inequivalence between something else? – Tsuyoshi Ito Feb 1 at 21:43
up vote 5 down vote

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

share|improve this answer
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}$$? – Kaveh♦ Jan 19 at 22:55
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...) – domotorp Jan 20 at 19:48
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? – Kaveh♦ Jan 20 at 20:02
Yes, perfectly. – domotorp Jan 21 at 8:09
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. – Kaveh♦ Jan 26 at 22:08

Your Answer

 
discard

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.