<p>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 <a href="https://eccc.weizmann.ac.il/report/2017/056/download/" rel="nofollow noreferrer">here</a>.</p>

CC BY-SA 3.0
2017-05-01T00:24:51.070Z
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.
Samuel Schlesinger
CC BY-SA 3.0
2017-05-01T00:26:34.377Z
Is it possible that no encoding of first order reductions like this exists? I find that incredibly difficult to believe...
Samuel Schlesinger
CC BY-SA 3.0
2017-05-01T02:33:30.457Z
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...
Joshua Grochow
CC BY-SA 3.0
2017-05-01T03:00:39.923Z
Errr each $f_i$ is a first order reduction so they can run in logarithmic space, and $L$ is in $coNP \cap NP$, so I feel like that is actually clear. Unless the encoding $i \mapsto f_i$ cannot be efficiently computed for some reason or another.
Samuel Schlesinger
CC BY-SA 3.0
2017-05-01T04:03:01.050Z
Ahhh right, so calling these reductions is probably not the best terminology, really these are just potential reductions, first order queries between string structures. Maybe it would make more sense if I used logspace reductions instead, as then it would just be an enumeration of logspace machines instead.
Samuel Schlesinger
CC BY-SA 3.0
2017-05-01T04:03:32.173Z
Unless what you're saying has another implication that I'm not seeing here? I think it stemmed from my bad terminology.
Samuel Schlesinger
CC BY-SA 3.0
2017-05-01T04:03:33.450Z
Oh, sorry, I misunderstood. Indeed, each f_i takes c_i log(n) space to compute. But unless I'm mistaken, the c_i are not bounded by a universal constant c, so the machine which on input $i$ runs a logspace machine for $f_i(i)$ uses more than log space... This applies even more so if you enumerate over logspace reductions.
Joshua Grochow
CC BY-SA 3.0
2017-05-01T04:06:05.083Z
Ay, there's the rub
Samuel Schlesinger
CC BY-SA 3.0
2017-05-01T04:12:18.493Z
With some thinking I may be able to get out of this or show conclusively that it is a problem in the $FO$ case, but it certainly is not alright a priori
Samuel Schlesinger
CC BY-SA 3.0
2017-05-01T04:25:44.737Z
Gave it a go, they're unbounded and you lose massive chunks of FO if you try to make it not so
Samuel Schlesinger
CC BY-SA 3.0
2017-05-01T04:27:55.137Z
Can you prove unconditionally that FO w/ $k$ quantifiers can't be computed in $(k-1)\log n$ space? That'd be the first place I'd look...
Joshua Grochow
CC BY-SA 3.0
2017-05-01T09:16:35.700Z
I’m voting to close as off-topic. This site is not meant to serve as a vetting place for alleged proofs.
Emil Jeřábek
CC BY-SA 3.0
2017-05-01T12:12:31.967Z
Yeah that's my bad, go for it
Samuel Schlesinger
CC BY-SA 3.0
2017-05-01T17:48:00.877Z
I've edited this so that it is a true question with motivation and placed my alleged proof in the answers.
Samuel Schlesinger
CC BY-SA 3.0
2017-05-02T00:26:29.737Z
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/on-topic].  3. Please don't use answers to post an alleged proof that you're hoping someone will vet for you.
D.W.
CC BY-SA 3.0
2017-05-02T00:29:58.567Z
Okay, I apologize. Will be more careful when posting again.
Samuel Schlesinger
<cc.complexity-theory><open-problem>
What progress is being made on $NP \cap coNP$ having complete problems?
Samuel Schlesinger
# What progress is being made on $NP \cap coNP$ having complete problems?

(Asked by: username_0 on 2017-05-01)

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](https://eccc.weizmann.ac.il/report/2017/056/download/).

**Tags:** cc.complexity-theory, open-problem

> **Comments:**
> **username_0**: 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.  
> **username_0**: Is it possible that no encoding of first order reductions like this exists? I find that incredibly difficult to believe...  
> **username_1**: 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...  
> **username_0**: Errr each $f_i$ is a first order reduction so they can run in logarithmic space, and $L$ is in $coNP \cap NP$, so I feel like that is actually clear. Unless the encoding $i \mapsto f_i$ cannot be efficiently computed for some reason or another.  
> **username_0**: Ahhh right, so calling these reductions is probably not the best terminology, really these are just potential reductions, first order queries between string structures. Maybe it would make more sense if I used logspace reductions instead, as then it would just be an enumeration of logspace machines instead.  
> **username_0**: Unless what you're saying has another implication that I'm not seeing here? I think it stemmed from my bad terminology.  
> **username_1**: Oh, sorry, I misunderstood. Indeed, each f_i takes c_i log(n) space to compute. But unless I'm mistaken, the c_i are not bounded by a universal constant c, so the machine which on input $i$ runs a logspace machine for $f_i(i)$ uses more than log space... This applies even more so if you enumerate over logspace reductions.  
> **username_0**: Ay, there's the rub  
> **username_0**: With some thinking I may be able to get out of this or show conclusively that it is a problem in the $FO$ case, but it certainly is not alright a priori  
> **username_0**: Gave it a go, they're unbounded and you lose massive chunks of FO if you try to make it not so  
> **username_1**: Can you prove unconditionally that FO w/ $k$ quantifiers can't be computed in $(k-1)\log n$ space? That'd be the first place I'd look...  
> **username_2**: I’m voting to close as off-topic. This site is not meant to serve as a vetting place for alleged proofs.  
> **username_0**: Yeah that's my bad, go for it  
> **username_0**: I've edited this so that it is a true question with motivation and placed my alleged proof in the answers.  
> **username_3**: 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/on-topic].  3. Please don't use answers to post an alleged proof that you're hoping someone will vet for you.  
> **username_0**: Okay, I apologize. Will be more careful when posting again.  

---

## 0 answers

