I am interesting in proving that there is no search problem that is polynomial bounded and self-reducible, as long as ${\sf P} \neq {\sf NP} \cap {\sf coNP}$.

The problem is I don't know how to approach the proof, below I wrote few ideas with open questions.

We can start by denoting the search problem in set ${\sf NP} \cap {\sf coNP}$ in terms of search problem relations $R_1$ and $R_2$ such that $S = \left \{ x:R_1(x) \neq \emptyset \right \} = \left \{ x:R_2(x) = \emptyset \right \} $. But how to present that the decision problem $S$ is not in ${\sf P}$. I don't know (but it seems to be crucial to show that $S$ is not in ${\sf P}$).

Having defined $S$ the next step would be to show that there is a relation $R$ that is self-reducible to $S$, but is not polynomial bounded.

In short, the question is how to define relation $R$ that is self-reducible to $S$. How to prove that $R$ is not polynomial bounded. Actually proving that $R$ is polynomial bounded may be redundant because $S$ is in ${\sf NP} \cap {\sf coNP}$ and it's given that ${\sf NP} \cap {\sf coNP} \neq {\sf P} $.

Addendum: I was given a hint

$R = \left \{ (x,1y):(x,y) \in R_1 \right \} \cup \left \{ (x,0y):(x,y) \in R_2 \right \}$

If I will be able to show that search problem relation R is self-reducible to S, than I think the problem is solved.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.