News for hackers. Stuff that matters.
Re:A proof P = NP was accidentally published in TOCT by munk-a on Monday July 19, 2021 @05:53PM (#27887673)
BRB computing several billion bitcoin hash completions on my Casio.
Re:A proof P = NP was accidentally published in TOCT by anyfoo on Monday July 19, 2021 @06:03PM (#27887778)
Serious question: Is computing cryptographic hashes, by any measure, actually NP-hard? Computing a single hash seems pretty constant to me. Or is there an alternative way to formulate the problem on a higher level, so that cracking cryptographic hashes is NP-hard?
Re:A proof P = NP was accidentally published in TOCT by staticassertion on Monday July 19, 2021 @06:07PM (#27887835)
Computing any hash isn't, but finding a preimage is NP.
Re:A proof P = NP was accidentally published in TOCT by anyfoo on Monday July 19, 2021 @06:17PM (#27887939)
Can you elaborate? Is it because a non-deterministic automaton would find the solution immediately (by trying all hashes at once), but a deterministic one of course wouldn't? I think I want to know in more detail why finding a pre-image is non-deterministically polynomial (though I might have answered that to myself with the sentence before), and more importantly why it's deterministically non-polynomial, and on what.

Annoying, I took theoretical computer science in university and used to have a better grasp on this, but apparently that part of complexity theory atrophied by now.

Re:A proof P = NP was accidentally published in TOCT by shadowgovt on Monday July 19, 2021 @06:40PM (#27888111)
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).

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.

Re:A proof P = NP was accidentally published in TOCT by anyfoo on Tuesday July 20, 2021 @02:38PM (#27897494)
That much was clear, and I believe also implied in my answers?
Re:A proof P = NP was accidentally published in TOCT by freemint on Tuesday July 20, 2021 @04:59PM (#27899250)
If what I said was your mental state then you are not wrong.