While thinking about natural language processing, I came up with the following NP problem:

OCCAM-k: Given a fixed natural number $k$, consider the following input: a natural number of states $S$ in unary in a Turing machine $M$, a finite collection $A$ of strings that $M$ accepts, and a finite collection $R$ of strings that $M$ rejects. Assuming that $M$ is polylimited by the polynomial $n^k+k$, that it contains at most $S$ states, that it accepts every string in $A$, and that it rejects every string in $R$, find a valid deterministic Turing machine that satisfies these conditions for $M$.

The problem is NP because after guessing a Turing machine $M$ of size $S = |S|$ ($S$ is unary), all that remains is to verify that the machine accepts every string in $A$ and rejects every string in $R$. Since $M$'s running time is bounded above by $n^k+k$, this can be accomplished in polynomial time.

I am skeptical that this problem is NP-complete, as I cannot think of an NP-complete problem that sounds likely to reduce to it in polynomial time. I would be excited if someone could prove that it is a member of P, as this would help with my motivation, which is to build a simple natural language processing system.

(My reason for calling the language OCCAM is that I believe that one could theoretically try to find a "natural language processing algorithm" that determines the binary truth value of sentences. Suppose I provided 1 million true natural-language sentences and 1 million false natural-language sentences as part of the input; I could try to find a small enough polytime algorithm that "gets all of these sentences right" and hope that the algorithm would work on all natural language sentences in that language (e.g., English)).

My question is: To which complexity class should we say OCCAM-k belongs? NP-complete? NPI? P? Is there an algorithm that could solve it?

  • 3
    $\begingroup$ I'm not an expert, but your "natural language processing algorithm" problem seems the core of a whole branch of TCS: Probably approximately correct learning (PAC). See for example this introduction $\endgroup$ – Marzio De Biasi Mar 6 '14 at 10:43
  • $\begingroup$ Great resource! Thanks. I hadn't heard of that before; I'll do some more research on it, it sounds quite relevant. $\endgroup$ – Philip White Mar 6 '14 at 10:51
  • $\begingroup$ While PAC learning is indeed close to the motivation part, I think it has little to do with the question as it is phrased. $\endgroup$ – domotorp Mar 6 '14 at 19:51
  • 1
    $\begingroup$ What if A and R are both singletons? I would guess already this problem is NP-complete. At least if there is no restriction on the running time of M, then it becomes undecidable. $\endgroup$ – domotorp Mar 6 '14 at 20:46
  • $\begingroup$ Is there a reduction like Cook-Levin from NP computations to this problem? Or a reduction from SAT? I couldn't think of how to do it myself. $\endgroup$ – Philip White Mar 6 '14 at 20:52

Your Answer

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

Browse other questions tagged or ask your own question.