Hacker News Reader

You don't need Turing machines for P and NP. Most reasonable models of computation are equivalent to Turing machines up to polynomial factors.

View on HN

I don't think you need to reach for Turing machines to specify P or NP, but I think it's fair to say that Turing machines* play a key role in establishing NP-completeness. (And other completeness phenomena.) Computational hardness is computational universality turned on its head, e.g. a problem X is NP-hard because someone has been able to figure out how to smuggle full-blown time-bounded nondeterministic Turing machines into instances of X.

*Or some other simple model of computation that's polynomially invariant wrt Turing machines, but at this point I don't think "you don't need Turing machines" remains as salient.

I meant that you don't need to know what a Turing machine is to understand what P and NP are or prove that a problem is NP-hard. I've seen a lot of people try to explain these concepts to lay audiences and Turing machines are almost never mentioned.

Fair. The topic is often taught to students without broaching the topic of Turing machines.

I think we agree that as a matter of actually building the topic of NP-completeness, nailing down a concrete model of computation for the verifiers which can itself be operated upon constructively is vital.

Reply on news.ycombinator.com