Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.