News for hackers. Stuff that matters.

A comment on The Power of One-State Turing Machines (2018). Parent comment

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 ]