The Power of One-State Turing Machines (2018)

Re:The Power of One-State Turing Machines (2018) by fnrslvr on Saturday November 23, 2019 @03:15PM (#21616242)

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.

[ Parent | on HN ]

Re:The Power of One-State Turing Machines (2018) by daveFNbuck on Sunday November 24, 2019 @10:49AM (#21621059)

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.

[ Parent | on HN ]

Re:The Power of One-State Turing Machines (2018) by fnrslvr on Sunday November 24, 2019 @01:38PM (#21622323)

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.

[ Parent | on HN ]