Comment by aphextron

Wouldn't that imply that P/NP is not a problem? All turing machines are capable of processing non-deterministic instructions, making them nothing like a state machine.