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.

After reading a related question, about non-constructive existence proofs of algorithms, I was wondering if there are methods of showing existence of "small" (say, state-wise) computation machines without actually building it.

Formally:

suppose we are given some language $L\subseteq \Sigma^*$ and fix some computation model (NFAs / turing machine/ etc.).

Are there any non-constructive existence results showing a $n$-state machine for $L$ exists, but without the ability of finding (in $poly(n,|\Sigma|)$ time) it?

For example, is there any regular language $L$ for which we can show $nsc(L)\leq n$ but we don't know how to build a $n$-state automaton for?

($nsc(L)$ is the non-deterministic state complexity of $L$, i.e. the number of states in the minimal NFA that accepts $L$).


EDIT: after some discussion with Marzio (thanks !) I think I can better formulate the question as follows:

Is there a language $L$ and a computation model for which the following holds:

  1. We know how to build a machine that compute $L$ that has $m$ states.

  2. We have a proof that $n$-states machine for $L$ exists (where $n << m$), but either we can't find it at all or it'd take exponential time to compute it.

share|improve this question
    
what is nsc(L)? the question seems related to compression/Kolmogorov complexity which asks to find small(est) machines to represent strings... –  vzn Apr 16 at 2:32
    
nsc(L) is the non deterministic state complexity of L (the number of states in the smallest NFA that accepts L). –  R B Apr 16 at 3:16
    
another idea/angle, maybe there are some "small" circuit classes (another computation model) for which it is proven they can calculate certain functions but the actual construction is tricky? SJ recently mentioned Barrington thm that width 5 branching programs can compute majority...? –  vzn Apr 16 at 4:11
    
@vzn The proof of Barrington's theorem give an easy procedure to convert formulas into branching programs. –  Sasho Nikolov Apr 16 at 5:02
1  
@RB: ok, you can find more interesting examples from resource bounded Kolmogorov complexity (in particular the time-bounded complexity). For example, given a string $x$, what is the smallest machine that runs in time $O(2^n)$ that prints $x$? In this case we can easily build a TM that prints $x$, but finding the smallest one requires to scan all the TMs $|M|<|x|$ (the time bound makes it computable). When I have more time, I'll expand my answer. –  Marzio De Biasi Apr 17 at 15:49
show 11 more comments

1 Answer 1

Only an extended comment with a trivial example; you can pick the one-element language:

$$L_k = \{ M \mid \sigma(M) = \Sigma(k) \}$$

i.e. $L_k$ contains the first (in lexicographical order) busy beaver Turing machine of size $k$ (the Turing machine of size $k$ that attains the largest number of 1s on its tape after halting).

For every $k$ the language $L_k$ is regular ... but we have no idea on how to build the small DFA that recognizes it (though it has only $\leq 2*k(\log k+2)$ states) :-)

share|improve this answer
    
While I agree it works, I was looking for existence showing techniques for explicitly given language L. –  R B Apr 15 at 23:08
1  
What is an "explicitly given language"? –  JɛffE May 1 at 11:26
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.