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.
$\begingroup$
$\endgroup$
16
-
$\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 SchlesingerMay 1, 2017 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 SchlesingerMay 1, 2017 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 GrochowMay 1, 2017 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řábekMay 1, 2017 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, 2017 at 0:26
|
Show 11 more comments