3 ms·
I think you're being unnecessarily pedantic. Yes, the P v. NP question pertains to Turing machines (and equivalent models), but in this case it is clear that th
by pron 10y ago
I think you're being unnecessarily pedantic. Yes, the P v. NP question pertains to Turing machines (and equivalent models), but in this case it is clear that there is an implied appeal to Physical + Complexity-Theoretic/Efficient/Extended Church-Turing Thesis. The paper explicitly says it relies on Cobham's thesis, which can be interpreted (if you squint) to encompass both extended interpretations of C-T.
You're right with regards to 1, but the actual paper does not make that mistake. Instead, it states correctly that the problem is NP-hard and therefore a feasible solution (i.e. P) would imply P = NP.