9 ms·
You basically have the right idea. The pre-image can be any arbitrary size (in fact, there are an infinite number of pre-images that will hash to the same value
by shadowgovt 5y ago
You basically have the right idea. The pre-image can be any arbitrary size (in fact, there are an infinite number of pre-images that will hash to the same value).
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).
- anyfoo 5y agoCorrect 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.
- freemint 5y agoA 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.