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?
Is the following Occam's razor decision problem a member of P?
ds.algorithms;complexity classes