11

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.

Community
  • 1
R B
  • 9,448
  • 5
  • 34
  • 74
  • 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 '14 at 02: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 '14 at 03: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 '14 at 04:11
  • @vzn The proof of Barrington's theorem give an easy procedure to convert formulas into branching programs. – Sasho Nikolov Apr 16 '14 at 05:02
  • @R B: A classical example is a probabilistic construction by Valiant (1984) of a small monotone formula for Majority. Similar are the construction of a deterministic circuit from a randomized one by Adleman (1978) as well as constructions based on the Isolation Lemma by Mulmuley-Vazirani-Vazirani (1987), and others. @vzn: Barrington's construction is indeed elementary - tricky (very!) is his "non-sequential" view at branching programs. – Stasys Apr 16 '14 at 10:24
  • the defn of "nonconstructive" can be tricky, but apparently nobody has actually built/exhibited width 5 branching programs for majority & (re SJs point) their behavior/function is not better or more directly understood/explained except via the Barrington thm construction. (for example a better understanding might lead to an inductive/recursive statement/formulation of their construction.) to me that is verging on "nonconstructive"... – vzn Apr 16 '14 at 15:27
  • A clarification: what do you mean with "exhaustive search of a Turing machine"? Human search? For example, in my answer, an exhaustive and automated search for an $L_k$ decider could be done only if we know the value of $\Sigma(k)$ or if we know a larger busy beaver or if we have an oracle for the halting problem or ....) – Marzio De Biasi Apr 17 '14 at 00:34
  • @MarzioDeBiasi - please let me know if this makes sense:

    In exponential time we can enumerate all of the $k$ states TM and find the busy beaver's machine. After which (now that we have the encoding) we can simply create a DFA for it, right?

    i.e. the reason we have no idea how to build the DFA at the moment is that we don't actually know the encoding of the TM of $L_k$.

     – R B Apr 17 '14 at 00:36
  • @RB: no, we cannot find the TM for $L_k$ with an automated procedure because the propert "M is a busy beaver of size k is undecidable"; we need to use an oracle for HALT (or know a larger busy beaver). In general deciding if a Turing machine computes a nontrivial language is undecidable, so if exhaustive search means automated exhaustive search you must put some restrictions on the model. – Marzio De Biasi Apr 17 '14 at 06:52
  • @MarzioDeBiasi - then it's even further than what I meant to ask for.

    I'm looking for a language $L$ for which we know how to build a machine for. Say with m states.

    Now I'm asking if there's a way of showing a smaller, n-state machine exists for the same language, but without being able to find it.

    Your answer gives a case where "n-state machine exist, but we don't know how to build any machine for it". I'm looking for a "n-state machine exist, but we can only build a m >> n states machine".

    Does it make sense? How'd you formulate it in the question? Thanks !

     – R B Apr 17 '14 at 14:04
  • 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 '14 at 15:49
  • @MarzioDeBiasi - That sounds good, but can we actually show an existence of a much smaller machine than the one we know how to build?

    Assume the trivial machine takes $m$ states, can we show that only $m$-states are needed for it?

    This is what I was aiming for - showing existence of a small machine where we know how to build a large one.

     – R B Apr 17 '14 at 23:41
  • @RB: most strings are incompressible (i.e. you need a TM larger than $|x|$ to print $x$) ... but at least some of them are highly compressible :-); take for example the binary representation of a number for which the prime factorization represenation is smaller: e.g. $n = 4^{56}7^{8*9}$ – Marzio De Biasi Apr 17 '14 at 23:55
  • @Stasys I think the examples you mentioned make for good answers. I was also thinking of Ajtai's probabilistic construction of depth 3 circuits for approximate majority. But then I realized Viola has given a uniform construction. – Sasho Nikolov Apr 18 '14 at 04:38
  • Regarding the revised question, what does "exponential time" mean? For instance, what if the language is finite? – András Salamon May 03 '14 at 15:54
  • @AndrásSalamon - suppose that the language $L$ is finite, and we have a $m$-states NFA for it, but a $n$-states NFA exists. Then in time $2^{O(m)}$ we can find the automaton in brute force manner (enumerate all $n$ state NFAs and check if it's equivalent to our $m$ states automaton), which is not what I'm after. – R B May 03 '14 at 16:53

3 Answers3

8

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

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
3

The language $ \mathtt{MOD_p} = \{a^{ip} \mid i \geq 0\} $ (for some prime number $p$) can be recognized by a $ O(\log p) $-state bounded-error quantum finite automata (QFAs) but the proof is non-constructive.

The best known constructively obtained number of states is $ O(\log^{2+o(1)}p) $ for bounded-error QFAs recognizing $ \mathtt{MOD_p} $.

REF: Section 4.2 of (Ambainis and Yakaryilmaz, 2015).

Abuzer Yakaryilmaz
  • 3,707
  • 1
  • 20
  • 38
2

Another solution is to use Higman's lemma:

A language closed under subwords is regular.

With $u$ a subword of $v$ if we can obtain $u$ by removing some letter in $v$.

So take any language L, its subword closure is regular but is not at all constructible since L is arbitrary.

C.P.
  • 992
  • 5
  • 12