'Finite' Approximation of Languages

Question

Is it true, that for any finite language, there is a Turing Machine that runs in polynomial time that accepts said language?

It seems to me that this would imply that given any number $N$, any language could be 'approximated' for inputs of length at most $N$ by a polynomial running time TM.

In particular, there should be an (effective) algorithm in P that correctly solves an NP-complete problem for inputs of length at most $N$.

Is the above correct? If it is indeed correct, what are some results regarding these kind of 'approximation'? Are there any 'approximating' algorithms with practical importance?

PS: sorry for my poor grammar.

Answer 1

While you're certainly correct that for any finite language $L$ there (abstractly) exists a Turing machine that runs in polynomial time (in fact, you can do as well as linear!), this doesn't necessarily mean that you can effectively solve NP-hard problems by truncating it.

To be explicit about the first part (a linear-time Turing machine that solves a given finite language $L$), you can consider the following algorithm:

• (preprocessing) construct a trie from all the strings in $L$
• now, given an input $x$, follow $x$ along the trie. If at any point the next character in $x$ is not contained in the trie, reject; otherwise, check that the node you end up at is an "accept" node and respond accordingly

Since you're just traversing a fixed tree for $|x|$-many steps, this is a linear time Turing machine. However, this doesn't mean that all languages can be effectively decided in linear time! The main issue is in constructing the Turing machine: given an NP-hard language $L$, suppose you truncate the problem to the (now linear-time solvable) finite language $L_{\leq N}$ of strings in $L$ of length $\leq N$. In theory, there exists a Turing machine that decides $L_{\leq N}$ in linear time, but how would you construct it without knowing $L_{\leq N}$ explicitly in the first place? To determine $L_{\leq N}$, you'd have to somehow decide for all strings $x$ of length $\leq N$ whether or not $x\in L$.

Basically, this insight can only get you this far:

Once you (somehow) determine the set of all length $\leq N$ strings contained in a language $L$, then you can solve $L_{\leq N}$ in linear time.

However, you can see how this is cheap: assuming you've determined $L_{\leq N}$, you just need to memorise this set (it's a finite set, so it would only take finite memory). This is similar to being able to check primality of all numbers $\leq N$ by just having a list of all prime numbers less than $N$: constructing this list remains a nontrivial (as in, takes more than linear time to do) task.

Analogously, consider the language $\mathsf{Halt}_{\leq N}$ of all pairs $(A,x)$ where $A$ is a Turing machine and $x$ is an input such that the encoding of this pair has length $\leq N$ and $A$ halts on $x$. It's still theoretically linear-time decidable, but how would you construct such a Turing machine?

Answer 2

Just consider that for any NP-complete language (assuming $P \ne NP$) you need a non-polynomial time to check if even a single word belongs to it... all that without any further details of what you want to do (that is precisely the crux of the matter: If $P \ne NP$, it is impossible to solve the "Is $\sigma \in L?$" question for all $\sigma$ in polynomial time).