Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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$.
share|improve this question
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 ? –  Marzio De Biasi Jan 31 at 17:32
    
That seems to work, perhaps make it an answer? –  András Salamon Jan 31 at 17:40
add comment

3 Answers

up vote 10 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
1  
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 Jan 31 at 17:50
    
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 Jan 31 at 17:58
    
@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 Jan 31 at 18:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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