News for hackers. Stuff that matters.
Re:A proof P = NP was accidentally published in TOCT by shadowgovt on Monday July 19, 2021 @05:31PM (#27887484)
BRB air gapping every single device I own and setting my internet router on fire. ;)
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.
Re:A proof P = NP was accidentally published in TOCT by smnrchrds on Monday July 19, 2021 @05:57PM (#27887723)
How will you be right back after that?
Re:A proof P = NP was accidentally published in TOCT by ineedasername on Monday July 19, 2021 @06:16PM (#27887925)
Assuming supplies on hand?

1)A 5 gallon bucket of gasoline

2) a shop vac w/o a filter & the hose stuck in the bucket to disperse it into the air as a fine mist

3) a bottle rocket sent through the front door (from across the street, preferably)

You know, I've never really though about how to make a homemade fuel air bomb before. It's a bit disturbing that it probably wouldn't be much harder than the above.

Re:A proof P = NP was accidentally published in TOCT by BenjiWiebe on Tuesday July 20, 2021 @01:41PM (#27896751)
The shop vac would probably actually ignite the fumes. And I think the GP was referring to the inability to be right back (here, online) after destroying his internet connection.