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.
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.
As useful rule of thumb, the way I learned to think about NP was the mnemonic "nifty proof." Problems in NP are not known to have a polynomial-time solution, and are not known to have no polynomial time solution; that's the million dollar question. What they are known to have is a polynomial time validation.
So it might take some heinous amount of time to find the pre-image of the hash, but determining if a given input string is the pre-image of the hash is polynomial on the number of characters in the pre-image (just run the hash function).