What is the computational-complexity-theoretic analogue of computable inseparability? For example, if P is not NP, are there disjoint NP sets with no separation in P? - MathOverflow

What is the computational-complexity-theoretic analogue of computable inseparability? For example, if P is not NP, are there disjoint NP sets with no separation in P?

2012-02-29T13:37:45Z

Disjoint sets $A$ and $B$ are computably inseparable, if there is no computable separating set, a computable set $C$ containing $A$ and disjoint from $B$. The existence of c.e. computably inseparable sets is a fundamental phenomenon explaining and unifing many arguments in computability theory.

Perhaps the easiest example of a c.e. computably inseparable pair of sets is the following, where $\varphi_e$ is the function computed by program $e$. $$A=\{e\mid \varphi_e(0)\downarrow =0\},\qquad B=\{e\mid \varphi_e(0)\downarrow=1\}.$$ To see this, suppose $C$ is decidable, $A\subset C$ and $B\cap C=\emptyset$. Since $C$ is computable, we may design via the recursion theorem a program $e$ such that $\varphi_e(0)\downarrow=1$ just in case $e\in C$, and otherwise $\varphi_e(0)=0$, and this gives an immediate contradiction. Another computably inseparable pair is the set of theorems versus the set of negations of theorems of PA, or your favorite consistent theory containing arithmetic.

Question. What is the computational-complexity-theoretic analogue of computable inseparability?

Specifically, if $P\neq NP$, then are there disjoint NP sets with no separating set in $P$?

This plainly fails if $P=NP$.

Edit. Mark Sapir points out that if we assume $\text{P}\neq\text{NP}\cap\text{Co-NP}$, then there is are some easy examples, namely, any set $L\in\text{NP}\cap\text{Co-NP}\setminus P$ together with its complement. In light of this (since this particular example won't help me with my intended purpose), let me modify the particular question to:

Question. Under some standard complexity theory hypothesis, such as $\text{P}\neq \text{NP}\cap\text{Co-NP}$, are there disjoint sets in NP with no separation in $\text{NP}\cap\text{Co-NP}$?

And are there other analogues of the phenomenon with other complexity classes?

Answer by Mark Sapir for What is the computational-complexity-theoretic analogue of computable inseparability? For example, if P is not NP, are there disjoint NP sets with no separation in P?

2012-02-29T13:58:00Z

If there is a set $L$ which is NP $\cap$ Co-NP but not in $P$, then $L$ and the complement of $L$ are both in NP and are inseparable. It is not known, of course, whether NP $\cap$ Co-NP=P.

Answer by Benjamin Steinberg for What is the computational-complexity-theoretic analogue of computable inseparability? For example, if P is not NP, are there disjoint NP sets with no separation in P?

2012-02-29T21:44:52Z

This should be a comment but is too long.

You may want to look at the literature on promise problems for NP-Disjoint pairs. They consider pairs (A,B) of disjoint NP-languages. One is to think of this as a promise that the words belonging to a language L belong to A and that none of the words in B belong to L. Then a P-language S with $A\subseteq S$ and $S\cap B=\emptyset$ is a polynomial time algorithm which on $A\cup B$ gets the correct answer and behaves arbitrarily on the remaining inputs. There seem to be a big literature on this. It seems if $P\neq UP$ (where UP is unambiguous polynomial time), there exist P-inseparable NP-sets. The assumption $P\neq UP$ is equivalent to the existence of a one-to-one worst-case one-way function. Apparently it is not known if $UP$ has complete problems. I am no expert on this.