# Are there known “completion” operations over languages ?

Assume that $P \neq NP$ and let $NPI = NP \setminus (P \cup NPC)$.

Let $L \in NPI$ be a language over an alphabet $\mathcal{A}$.

Does there always exist $S \subset \mathcal{A}^*$ such as $(L \cup S) \in NPC$ ?

On the removal side, Ladner showed that for each $L \in NPI$, there exists $S \subset L$, $S \neq L$ such as $S \in NPI$.

What are known theorems around those kind of operations ?

• I assume you are using NPI to refer to a problem in NP not known to be NPC ? Also, in the reference to Ladner, do you perhaps mean that L is NPC, and the removal S is NPI ? – Suresh Venkat Aug 28 '10 at 9:23
• Ladner showed 2 things : for SAT, there is a subset which is in NPI, and for an NPI language, there is a strict subset which is still in NPI. I'll edit my question to precise what NPI is. – Ludovic Patey Aug 28 '10 at 9:27
• Let w be string not in L, add let S be wSAT (w concatenated with strings in SAT). The union will be NP-complete. – Kaveh Aug 28 '10 at 10:55
• I guess you are asking about the structure of NP-degrees (equivalence classes of sets in NP). I think there should be papers on this from the recursion theoretic period of complexity theory, don't know if they are interesting. – Kaveh Aug 28 '10 at 11:00
• @ Monoïd, please clarify whether S is in NPI – Mohammad Al-Turkistany Aug 28 '10 at 17:41

Some observations:

1) For any NPI set $L$, there is an isomorphic set $L'$ and a set $S$ such that $L' \cup S$ is NP-complete. Let $L' = \{0x : x \in L\}$ and let $S = \{ 1x : x \in SAT \}$. This observation applies in a more direct manner to some of the natural suspected NPI sets (such as $GA$ -- see my comments on turkistany's answer). It will also apply to the padded version of any set in $NEXP \backslash EXP$ (assuming $NEXP \neq EXP$, such a set is in NPI), for most reasonable ways of padding sets.

This rasises a potentially interesting question:

Is it the case that for any $L \in NPI$, there is an isomorphic language $L'$ and a set $S$ that is not NP-complete such that $L' \cup S$ is NP-complete?

2) R. Downey and L. Fortnow. Uniformly hard languages. Theoretical Computer Science, 298(2):303-315, 2003 (available from Lance's web page). They show that the current proofs of Ladner's Theorem cannot easily be modified to produce uniformly hard languages (their definition of uniform hardness is natural, but is also in a sense aimed at Ladner-type constructions; it is not simply almost-everywhere hardness). In particular, they show that if $P = PSPACE$ there is a minimal uniformly hard language under honest reductions; in particular, there is no relativizing proof of Ladner's Theorem for honest p-degrees that produces uniformly hard languages.

In particular, that means that any relativizing proof of Ladner's Theorem that works for honest p-degrees (all known proofs fall in this category) produces sets with arbitrary polynomially-long stretches where they look like a set in $P$. Now, that's not quite enough to be able to say that if $L$ is a language produced by such a construction then there is a set $S$ such that $L \cup S$ is NP-complete, but it's pretty close.

• I think the idea can be extended to work for the stronger version you mentioned if SAT is union of two NPI sets. – Kaveh Aug 28 '10 at 19:14
• Kaveh, interesting thought; can you expand on your idea? Certainly having SAT (or some NPC set) be the union of two NPI sets is a necessary condition for the stronger version. But at the moment I'm having trouble seeing that it's sufficient. – Joshua Grochow Aug 29 '10 at 6:01
• This was my idea but it is not a complete solution as $L'$ is not isomorphic to $L$: Assume $SAT=A\cup B$, where $A$ and $B$ are $NPI$. Let $L$ be an arbitrary $NPI$ set. Let $L'=00A \cup 1L$ and $S=01B$. $L'$ and $S$ are $NPI$ and their union contains a copy of $SAT$ and is therefore $NP-complete$. – Kaveh Sep 1 '10 at 12:30
• The problem is my idea above gives an $L'$ that can be not Karp reducible to $L$, but I think it should be if $L'$ needs to be isomorphic to $L$. Without further developments the idea only works for those $L$ for which there is a split of $SAT$ into two sets s.t. at least one of them is Karp reducible to $L$. – Kaveh Sep 1 '10 at 12:37