Re:A proof P = NP was accidentally published in TOCT
by anyfoo on Monday July 19, 2021 @06:43PM
(#27888136)
Correct me if I'm wrong: So n is actually the size of the hash. That's indeed exponential if you try to brute force it, but a non-deterministic automaton would still give the answer immediately.
[ Parent
| on HN ]
Re:A proof P = NP was accidentally published in TOCT
by freemint on Tuesday July 20, 2021 @06:18AM
(#27891931)
A non-deterministic automata can you give an answer after n steps which is polynomial.
NP is the class of problems that can be solved in polynomial time by a non-deterministic automaton.