<p>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.)</p>

<p>Then the answer is negative in a relativized world.</p>

<p>The statement TFNP ⊆ FP is known as <em>Proposition Q</em> in the literature [FFNR03].  There is a weaker statement called <em>Proposition Q’</em> [FFNR03] that every total <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aN#npmv" rel="nofollow">NPMV</a> relation with one-bit answers is in FP.  (Here a <em>relation with one-bit answers</em> means a subset of {0,1}<sup>*</sup>×{0,1}.)  It is easy to see that Proposition Q relative to some oracle implies Proposition Q’ relative to the same oracle.</p>

<p>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.</p>

<h2>References</h2>

<p>[FFNR03] Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, and John D. Rogers.  Inverting onto functions.  <em>Information and Computation</em>, 186(1):90–103, Oct. 2003.  DOI: <a href="http://dx.doi.org/10.1016/S0890-5401%2803%2900119-6" rel="nofollow">10.1016/S0890-5401(03)00119-6</a>.</p>

<p>[FR02] Lance Fortnow and John D. Rogers.  Separability and one-way functions.  <em>Computational Complexity</em>, 11(3–4):137–157, June 2002.  DOI: <a href="http://dx.doi.org/10.1007/s00037-002-0173-4" rel="nofollow">10.1007/s00037-002-0173-4</a>.</p>

CC BY-SA 3.0
2013-02-01T17:56:10.223Z
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](http://dx.doi.org/10.1006/jcss.1998.1575)", 1998
Kaveh
CC BY-SA 3.0
2013-02-01T17:57:48.957Z
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
CC BY-SA 3.0
2013-02-01T20:30:35.603Z
@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
CC BY-SA 3.0
2013-02-01T21:24:08.323Z
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
CC BY-SA 3.0
2013-02-01T21:43:01.993Z
@Kaveh: Are you talking about inequivalence between two propositions “P=NP∩coNP” and “TFNP⊆FP,” or inequivalence between something else?
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-30T22:38:19.693Z
2013-01-31T22:45:32.240Z
2013-01-31T22:45:32.240Z
Tsuyoshi Ito
<p>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$. </p>

CC BY-SA 3.0
2013-01-19T22:55:57.287Z
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
CC BY-SA 3.0
2013-01-20T19:48:54.807Z
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
CC BY-SA 3.0
2013-01-20T20:02:35.303Z
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
CC BY-SA 3.0
2013-01-21T08:09:42.937Z
Yes, perfectly.
domotorp
CC BY-SA 3.0
2013-01-26T22:08:27.517Z
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
CC BY-SA 3.0
2013-01-19T08:43:59.990Z
2013-01-19T09:06:11.803Z
2013-01-19T09:06:11.803Z
domotorp
<p>It easy to see that if $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$ then there are <a href="http://en.m.wikipedia.org/wiki/TFNP">total $\mathsf{NP}$ search problems</a> which cannot be solved in polynomial time (create a total search problem by having both the witnesses for membership and the witnesses for nonmembership).</p>

<p>Is the converse also true, i.e. </p>

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

CC BY-SA 3.0
2013-01-19T12:24:09.387Z
Do you mean a total search problem with NP decision problem? Is integer factorization such problem?
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-01-19T14:35:01.420Z
I think he means TFNP.
domotorp
<cc.complexity-theory><reference-request><search-problem>
Does existence of a total $\mathsf{NP}$ search problem not solvable in polytime imply $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$?
Kaveh
# Does existence of a total $\mathsf{NP}$ search problem not solvable in polytime imply $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$?

(Asked by: username_0 on 2013-01-19)

It easy to see that if $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$ then there are [total $\mathsf{NP}$ search problems](http://en.m.wikipedia.org/wiki/TFNP) 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}$?

**Tags:** cc.complexity-theory, reference-request, search-problem
> **Comments:**
> **username_1**: Do you mean a total search problem with NP decision problem? Is integer factorization such problem?  
> **username_2**: I think he means TFNP.  

---

## 2 answers

### Answer by username_3 on 2013-01-30. Score: 4 | Accepted answer

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](https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aN#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](http://dx.doi.org/10.1016/S0890-5401%2803%2900119-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](http://dx.doi.org/10.1007/s00037-002-0173-4).

> **Comments:**
> **username_0**: 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](http://dx.doi.org/10.1006/jcss.1998.1575)", 1998  
> **username_0**: 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$.  
> **username_3**: @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.  
> **username_0**: 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}}$.  
> **username_3**: @Kaveh: Are you talking about inequivalence between two propositions “P=NP∩coNP” and “TFNP⊆FP,” or inequivalence between something else?  

---

### Answer by username_2 on 2013-01-19. Score: 5

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

> **Comments:**
> **username_0**: 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}$$?  
> **username_2**: 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...)  
> **username_0**: 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?  
> **username_2**: Yes, perfectly.  
> **username_0**: 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.  

---

