3 ms·

Sounds like you're not a scientist or a mathematician then. No problem there. But why litter a discussion clearly not meant for you with rude and irrelevant com

by j2kun 12y ago

Sounds like you're not a scientist or a mathematician then. No problem there. But why litter a discussion clearly not meant for you with rude and irrelevant comments? Breaking hashing functions is not related to the article, nor is it equivalent to the problem of P versus NP.

deleted 12y ago
[deleted]
- rspeer 12y ago
  Nobody's objecting to the swearing part, I promise you. Seriously, what in the world made you decide to read and comment on a Scott Aaronson article if you don't believe in theoretical computer science?
- tlarkworthy 12y ago
  P Vs. NP isn't just of consequence to cryptography. It's extremely relevant to scheduling and resource use optimization. E.g. FedEx want to deliver parcels as fast as possible. Factories should be laid out optimally, chips should have their internal wiring minimized etc. Those all have NP problems underneath them and improvements to computing in that category would have huge economic benefits (although it ain't gonna happen)
- j2kun 12y ago
  You're missing my point, which is that the existence of cryptographically secure hashing functions is not equivalent to P != NP. So even if someone were to prove that there are no secure hashing functions (which you would be fine with so long as reversal takes a long time in real life), this would not necessarily resolve P versus NP. I would suggest you read more about one-way functions and how theoretical cryptography relates to complexity theory, but you don't seem to take mathematical inquiry very seriously. Again, it's not a problem, but you should consider it a prerequisite for having serious discussions about P versus NP if you insist on relating it to hashing.
xxxyy 12y ago
Breaking polynomially computable hashes is in NP, in the sense that its decision version - is there any word lexicographicaly smaller than w that hashes out to v - is in the NP class. Thus P=NP would give us a procedure to compute preimages of all known reasonable hash functions, with complexity depending on the size of the shortest solution.
- j2kun 12y ago
  That is one implication. But as I explained in my other comment, the nonexistence of one-way functions does not imply the resolution of P versus NP. So the two problems are not equivalent.

by j2kun 12y ago

deleted 12y ago

[deleted]

rspeer 12y ago
Nobody's objecting to the swearing part, I promise you. Seriously, what in the world made you decide to read and comment on a Scott Aaronson article if you don't believe in theoretical computer science?
tlarkworthy 12y ago
P Vs. NP isn't just of consequence to cryptography. It's extremely relevant to scheduling and resource use optimization. E.g. FedEx want to deliver parcels as fast as possible. Factories should be laid out optimally, chips should have their internal wiring minimized etc. Those all have NP problems underneath them and improvements to computing in that category would have huge economic benefits (although it ain't gonna happen)
j2kun 12y ago
You're missing my point, which is that the existence of cryptographically secure hashing functions is not equivalent to P != NP. So even if someone were to prove that there are no secure hashing functions (which you would be fine with so long as reversal takes a long time in real life), this would not necessarily resolve P versus NP. I would suggest you read more about one-way functions and how theoretical cryptography relates to complexity theory, but you don't seem to take mathematical inquiry very seriously. Again, it's not a problem, but you should consider it a prerequisite for having serious discussions about P versus NP if you insist on relating it to hashing.

xxxyy 12y ago

Breaking polynomially computable hashes is in NP, in the sense that its decision version - is there any word lexicographicaly smaller than w that hashes out to v - is in the NP class. Thus P=NP would give us a procedure to compute preimages of all known reasonable hash functions, with complexity depending on the size of the shortest solution.

j2kun 12y ago
That is one implication. But as I explained in my other comment, the nonexistence of one-way functions does not imply the resolution of P versus NP. So the two problems are not equivalent.