<p>Some observations:</p>

<p>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.</p>

<p>This rasises a potentially interesting question: </p>

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

<p>2) R. Downey and L. Fortnow. Uniformly hard languages. Theoretical Computer Science, 298(2):303-315, 2003 (<a href="http://people.cs.uchicago.edu/~fortnow/papers/uniform.pdf" rel="nofollow">available from Lance's web page</a>).  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.  </p>

<p>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.</p>

CC BY-SA 2.5
2010-08-28T19:14:41.757Z
I think the idea can be extended to work for the stronger version you mentioned if SAT is union of two NPI sets.
Kaveh
CC BY-SA 2.5
2010-08-29T06:01:39.090Z
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
CC BY-SA 2.5
2010-09-01T12:30:37.343Z
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
CC BY-SA 2.5
2010-09-01T12:37:30.573Z
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
CC BY-SA 2.5
2010-08-28T18:27:28.303Z
2010-08-28T18:27:28.303Z
Joshua Grochow
<p>Assume that $P \neq NP$ and let $NPI = NP \setminus (P \cup NPC)$.</p>

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

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

<p>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$.</p>

<p>What are known theorems around those kind of operations ?</p>

CC BY-SA 2.5
2010-08-28T09:23:57.127Z
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
CC BY-SA 2.5
2010-08-28T09:27:45.897Z
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
CC BY-SA 2.5
2010-08-28T10:55:29.220Z
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
CC BY-SA 2.5
2010-08-28T11:00:55.093Z
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
CC BY-SA 2.5
2010-08-28T17:41:41.090Z
@ Monoïd, please clarify whether S is in NPI
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-04T19:34:45.217Z
For the first part ($S \subset \mathcal{A}^*$), I don't make assomptions wether S is in NPI or not. For the Ladner result, I confirm S is in NPI, even if it isn't the main result of his paper.
Ludovic Patey
<cc.complexity-theory><complexity-classes>
Are there known "completion" operations over languages ?
Ludovic Patey
# Are there known "completion" operations over languages ?

(Asked by: username_0 on 2010-08-28)

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 ?

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: 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 ?  
> **username_0**: 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.  
> **username_2**: Let w be string not in L, add let S be wSAT (w concatenated with strings in SAT). The union will be NP-complete.  
> **username_2**: 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.  
> **username_3**: @ Monoïd, please clarify whether S is in NPI  
> **username_0**: For the first part ($S \subset \mathcal{A}^*$), I don't make assomptions wether S is in NPI or not. For the Ladner result, I confirm S is in NPI, even if it isn't the main result of his paper.  

---

## 1 answers

### Answer by username_4 on 2010-08-28. Score: 3 | Accepted answer

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](http://people.cs.uchicago.edu/~fortnow/papers/uniform.pdf)). 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.

> **Comments:**
> **username_2**: I think the idea can be extended to work for the stronger version you mentioned if SAT is union of two NPI sets.  
> **username_4**: 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.  
> **username_2**: 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$.  
> **username_2**: 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$.  

---

