4 ms·

Computing any hash isn't, but finding a preimage is NP.

anyfoo 5y ago
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.
- deleted 5y ago
  [deleted]
- 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 ago
    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.
    - freemint 5y ago
      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.
      - anyfoo 5y ago
        That much was clear, and I believe also implied in my answers?
        freemint 5y ago
        If what I said was your mental state then you are not wrong.

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.

deleted 5y ago
[deleted]
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 ago
  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.
  - freemint 5y ago
    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.
    - anyfoo 5y ago
      That much was clear, and I believe also implied in my answers?
      - freemint 5y ago
        If what I said was your mental state then you are not wrong.