Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Note of clarification.

This authors use of 'non-determinsistic' doesn't match the meaning of a Nondeterministic Turing machine used to define the complexity class NP.

There are many types of non-deterministic Turing machines, like a probabilistic Turing machine which flips a coin at each step.

But the 'maximally lucky guesser' or 'run all possibilities in one step' version of NTM's that defines NP is physically unrealizable.



It is the same notion exactly actually.

The code isn't magically solving NP vs P but it does simulate non deterministic run through a potentially exponential exploration.


It's roughly the same, no? It emulates a non-deterministic Turing machine and gives the same results, just taking much longer. But runtime isn't everything! I think that if you're programming in a nondeterministic style, you're programming as if you have a NTM, whether or not you're actually running the code on one.

Also, surely NTMs are only physically unrealizable if P!=NP, and so whether or not NTMs could exist is an open question.




Consider applying for YC's Winter 2026 batch! Applications are open till Nov 10

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: