Hacker News Reader

Comment by gregorygoc | Hacker News Reader

So the cool stuff about Turing machines is that if you get them, then you get a theoretical model of computation. And based on this knowledge you can really understand some problems, say is P = NP? Or maybe you encounter some problem at work and you cannot find an efficient algorithm to it, so you might try to prove that the thing you are working on is NP-hard (making it non trivially solvable in human words).

View on HN

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

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