11
$\begingroup$

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?

$\endgroup$

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
1
5
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\begingroup$ The existence of inseparable disjoint NP pairs is considered a complexity assumption on its own, and it is not known to be implied by P ≠ NP. $\endgroup$ Feb 29, 2012 at 14:12
  • 1
    $\begingroup$ @Mark: NP ∩ Co-NP ≠ P is probably a little more standard because factoring (suitably formulated as a decision problem) is in NP ∩ Co-NP. $\endgroup$ Feb 29, 2012 at 16:10
  • 1
    $\begingroup$ @Mark: To generalize Timothy’s comment, $NP\cap coNP\ne P$ is implied by the existence of one-way permutations. @Joel: I don’t think the existence of disjoint NP sets not separated by a $NP\cap coNP$ set is a standard assumption, nevertheless I’m pretty sure it’s an open problem, even assuming $NP\cap coNP\ne P$. $\endgroup$ Feb 29, 2012 at 17:56
  • 1
    $\begingroup$ @Mark: Are you losing the train of thought here? What I was addressing was which of NP ∩ Co-NP ≠ P and NP ∩ Co-NP = P is "more standard"; presumably that means "more widely believed." I'm confident that more people believe in the existence of one-way permutations (note: permutations and not functions) than don't. $\endgroup$ Mar 1, 2012 at 15:55
  • 1
    $\begingroup$ @Timothy: I am not sure which comment you are referring to. Yes, most CS people I know are trying to construct a one-way permutation. I think this is because trying to prove that there are none is completely hopeless. I may be wrong. Anyway, there is no proof either way, so this is pure speculation. There was time when thinking that the Earth is flat was pretty standard. $\endgroup$
    – user6976
    Mar 1, 2012 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.