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$.
  • 1
    $\begingroup$ 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 ? $\endgroup$ Jan 31 '14 at 17:32
  • $\begingroup$ That seems to work, perhaps make it an answer? $\endgroup$ Jan 31 '14 at 17:40

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).


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$.)


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

  • 1
    $\begingroup$ 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. $\endgroup$ Jan 31 '14 at 17:50
  • $\begingroup$ 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. $\endgroup$ Jan 31 '14 at 17:58
  • $\begingroup$ @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. $\endgroup$ Jan 31 '14 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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