I'm very curious about this and have a proof sketch that it does not in the answers below. The reasons I'm currently thinking about this is because of the new paper on the class $PTFNP$ which can be downloaded here.


closed as off-topic by Joshua Grochow, Emil Jeřábek, Sasho Nikolov, D.W., Kaveh May 2 '17 at 1:31

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Joshua Grochow, Emil Jeřábek, Sasho Nikolov
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Assuming that $P = NP$, $NP \cap coNP = P$ and thus has complete problems. Thus my proof used diagonalization to show that $P \neq NP$, so it really must be wrong. I would love to know why. $\endgroup$ – Samuel Schlesinger May 1 '17 at 0:24
  • $\begingroup$ Is it possible that no encoding of first order reductions like this exists? I find that incredibly difficult to believe... $\endgroup$ – Samuel Schlesinger May 1 '17 at 0:26
  • 2
    $\begingroup$ The FO part isn't the issue. The issue is where you say "Clearly we have that $D \in NP \cap coNP$." "Clearly" should always be the first place you look for a hole in a proof you think has a hole :), and indeed there is one here. Ask yourself: what is the running time of $f_i$? Unfortunately, though the question was asked earnestly by someone who knows what they're talking about, this turns out to not be a research-level question... $\endgroup$ – Joshua Grochow May 1 '17 at 2:33
  • 2
    $\begingroup$ I’m voting to close as off-topic. This site is not meant to serve as a vetting place for alleged proofs. $\endgroup$ – Emil Jeřábek May 1 '17 at 9:16
  • 2
    $\begingroup$ 1. Please don't edit the question to radically change its meaning. At that point it would be better to delete this question and ask a new one. 2. The updated question is probably too broad. What research have you done? Have you done a literature search? See the 'Questions should be based on..' section of our help center. 3. Please don't use answers to post an alleged proof that you're hoping someone will vet for you. $\endgroup$ – D.W. May 2 '17 at 0:26