3 ms·
You don't need Turing machines for P and NP. Most reasonable models of computation are equivalent to Turing machines up to polynomial factors.
by daveFNbuck 7y ago
You don't need Turing machines for P and NP. Most reasonable models of computation are equivalent to Turing machines up to polynomial factors.
- fnrslvr 7y agoI 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.
- daveFNbuck 7y agoI 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.
- fnrslvr 7y agoFair. 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.