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?