<p>Just to add to Marzio's and usul's answers: the same can be done even if one wants to require that the difference between $L_s$ and $L_{s+1}$ be an infinite set (which is one way to try to make the question less trivially answered, but, as we see, doesn't work). Let $D_n = \{ x \in \{0,1\}^* : 1x \text{ is the binary expansion of an integer divisible by } n\}$. Then taking $L_0 = L$ and $L_{s+1} = L_s \cup D_s$ should do the trick.</p>

<p>(For any fixed $s$, if $L$ was, say, CLIQUE, it should be relatively easy to take a reduction from SAT to CLIQUE and modify it by something like padding so that it is still a reduction from SAT to CLIQUE$\cup D_s$.)</p>

CC BY-SA 3.0
2014-02-01T02:01:57.423Z
2014-02-01T02:01:57.423Z
Joshua Grochow
<p>Given an enumeration $\varphi_1, \varphi_2,...$ of binary encoded boolean formulas define $L_s = SAT \cup \{ \varphi_{i_1},...,\varphi_{i_s}\}$ where $\varphi_{i_1},...,\varphi_{i_s}$ are the first $s$ unsatisfiable formulas in the enumeration.</p>

<p>$L_s$ is clearly hard for $NP$: given a boolean formula $\varphi$ add to it enough new OR-ed variables $x_i$   $\varphi \lor x_1 \lor ... \lor x_n$ until its index in the enumeration becomes greater than (constant) $i_s$.</p>

CC BY-SA 3.0
2014-01-31T17:50:57.667Z
On second thoughts, this seems to require an encoding for which every finite word is guaranteed to appear as the encoding of some CNF formula.  However, one could then modify the second condition so that $L$ is the language of all syntactically valid CNF formulas in the encoding; this still captures the spirit of the question.
András Salamon
CC BY-SA 3.0
2014-01-31T17:58:27.393Z
For hardness, it seems sufficient to observe that if $L$ is NP-hard, and $L'$ is a finite language, then $L \cup L'$ is also NP-hard.
András Salamon
CC BY-SA 3.0
2014-01-31T18:08:33.530Z
@AndrásSalamon: you're right about hardness proof :-S ! However I think that a "perfect" encoding (a bijection between N and all valid formulas) is possible and computable in polynomial time.
Marzio De Biasi
CC BY-SA 3.0
2014-01-31T17:41:48.927Z
2014-01-31T17:47:22.703Z
2014-01-31T17:47:22.703Z
Marzio De Biasi
<p>I think we can just start with some base language $L$, then take $L_0 = L$ and $L_{s+1} = L_s \cup \{0,1\}^{s+1}$.</p>

<p>That is, each $L_s$ is the union of $L$ with all strings of length up to $s$. Each $L_s$ is at least as hard as $L$ but is no harder (in an asymptotic sense), assuming we can count to $s$.</p>

<p>I also thought about the opposite "limit", so each $L_{s+1}$ is contained in $L_s$, and $L = \cap_s L_s$ is easy while each $L_s$ is hard. But I think we could just start with a hard (but countable) language $L_0$ and just remove one word at each step; the intersection should be empty (every word is eventually removed).</p>

CC BY-SA 3.0
2014-02-01T01:19:02.883Z
2014-02-01T01:19:02.883Z
usul
<p>Can the following all hold simultaneously?</p>

<ol>
<li>$L_s$ is contained in $L_{s+1}$ for all positive integers $s$.</li>
<li>$L = \bigcup_s L_s$ is the language of all finite words over $\{0,1\}$.</li>
<li>There is some complexity class $C$ and a notion of reduction appropriate for $C$ such that for each $s$, $L_s$ is hard for $C$.</li>
</ol>

CC BY-SA 3.0
2014-01-31T17:32:51.680Z
Can this work? Given an enumeration $\varphi_1, \varphi_2,...$ of (binary encoded) boolean formulas define $L_s = SAT \cup \{ \varphi_{i_1},...,\varphi_{i_s}\}$ where $\varphi_{i_1},...,\varphi_{i_s}$ are the first $s$ unsatisfiable formulas in the enumeration ?
Marzio De Biasi
CC BY-SA 3.0
2014-01-31T17:40:10.910Z
That seems to work, perhaps make it an answer?
András Salamon
<cc.complexity-theory><complexity-classes><reductions>
Can limit of hard languages be easy?
András Salamon
# Can limit of hard languages be easy?

(Asked by: username_0 on 2014-01-31)

Can the following all hold simultaneously?

1. $L\_s$ is contained in $L\_{s+1}$ for all positive integers $s$.
2. $L = \bigcup\_s L\_s$ is the language of all finite words over $\{0,1\}$.
3. There is some complexity class $C$ and a notion of reduction appropriate for $C$ such that for each $s$, $L\_s$ is hard for $C$.

**Tags:** cc.complexity-theory, complexity-classes, reductions
> **Comments:**
> **username_1**: Can this work? Given an enumeration $\varphi_1, \varphi_2,...$ of (binary encoded) boolean formulas define $L_s = SAT \cup \{ \varphi_{i_1},...,\varphi_{i_s}\}$ where $\varphi_{i_1},...,\varphi_{i_s}$ are the first $s$ unsatisfiable formulas in the enumeration ?  
> **username_0**: That seems to work, perhaps make it an answer?  

---

## 3 answers

### Answer by username_3 on 2014-02-01. Score: 10 | Accepted answer

I think we can just start with some base language $L$, then take $L\_0 = L$ and $L\_{s+1} = L\_s \cup \{0,1\}^{s+1}$.

That is, each $L\_s$ is the union of $L$ with all strings of length up to $s$. Each $L\_s$ is at least as hard as $L$ but is no harder (in an asymptotic sense), assuming we can count to $s$.

I also thought about the opposite "limit", so each $L\_{s+1}$ is contained in $L\_s$, and $L = \cap\_s L\_s$ is easy while each $L\_s$ is hard. But I think we could just start with a hard (but countable) language $L\_0$ and just remove one word at each step; the intersection should be empty (every word is eventually removed).


---

### Answer by username_2 on 2014-02-01. Score: 7

Just to add to Marzio's and usul's answers: the same can be done even if one wants to require that the difference between $L\_s$ and $L\_{s+1}$ be an infinite set (which is one way to try to make the question less trivially answered, but, as we see, doesn't work). Let $D\_n = \{ x \in \{0,1\}^\* : 1x \text{ is the binary expansion of an integer divisible by } n\}$. Then taking $L\_0 = L$ and $L\_{s+1} = L\_s \cup D\_s$ should do the trick.

(For any fixed $s$, if $L$ was, say, CLIQUE, it should be relatively easy to take a reduction from SAT to CLIQUE and modify it by something like padding so that it is still a reduction from SAT to CLIQUE$\cup D\_s$.)


---

### Answer by username_1 on 2014-01-31. Score: 4

Given an enumeration $\varphi\_1, \varphi\_2,...$ of binary encoded boolean formulas define $L\_s = SAT \cup \{ \varphi\_{i\_1},...,\varphi\_{i\_s}\}$ where $\varphi\_{i\_1},...,\varphi\_{i\_s}$ are the first $s$ unsatisfiable formulas in the enumeration.

$L\_s$ is clearly hard for $NP$: given a boolean formula $\varphi$ add to it enough new OR-ed variables $x\_i$ $\varphi \lor x\_1 \lor ... \lor x\_n$ until its index in the enumeration becomes greater than (constant) $i\_s$.

> **Comments:**
> **username_0**: On second thoughts, this seems to require an encoding for which every finite word is guaranteed to appear as the encoding of some CNF formula.  However, one could then modify the second condition so that $L$ is the language of all syntactically valid CNF formulas in the encoding; this still captures the spirit of the question.  
> **username_0**: For hardness, it seems sufficient to observe that if $L$ is NP-hard, and $L'$ is a finite language, then $L \cup L'$ is also NP-hard.  
> **username_1**: @AndrásSalamon: you're right about hardness proof :-S ! However I think that a "perfect" encoding (a bijection between N and all valid formulas) is possible and computable in polynomial time.  

---

