-1
$\begingroup$

What is the input of a given hash?

The problem can be verified in polynomial time (using a hash that executed in polynomial time), and I suspect that it may be possible to prove that there is no algorithm that can solve it in polynomial time.

Take a binary string $X$ of length $n$.
The number of possible values for $X$ is $2^n$.
Solving the problem by using a hash table still involves initially calculating the hashes for all $2^n$ variations, so I'm not sure if it can be counted. But if hash tables are permitted, and generation of the hash table is not included in the cost, then time complexity goes down to $O(n)$, (binary search on the elements of the (sorted) hash table gives a time complexity of $O(\log(2^n)) = O(n)$.
 
I feel if we permit hash tables to reduce the asymptotic complexity, then we should permit similar methods to reduce the asymptotic complexity of problems. Hash table generation is $O(2^n)$ and I feel this should be accounted for.

Improve this question
$\endgroup$
5
  • $\begingroup$ Does the problem "what is the input of a given hash" offer any insight into P vs NP. I suspect it's a (valid) counterexample to "P = NP"; is it? $\endgroup$
    – Tobi Alafin
    Jul 6, 2017 at 8:25
  • $\begingroup$ Technically P and NP are concerned with decision problems. The way you stated your problem, it is in neither class. $\endgroup$
    – Merzhase
    Jul 6, 2017 at 15:31
  • $\begingroup$ @HennerHinze This is true but the problem doesn't have to be in either class to have implications for P vs NP. For example, the optimization problem "Tell me the size of the largest clique in the input graph" isn't in P or NP but a polynomial-time algorithm for it would still imply P=NP. $\endgroup$
    – David Richerby
    Jul 6, 2017 at 15:46
  • $\begingroup$ Which hashing algorithm do you assume? $\endgroup$
    – Raphael ♦
    Jul 6, 2017 at 19:04
  • $\begingroup$ A cryptographic hash function that satisfies Wikipedia's five criteria. $\endgroup$
    – Tobi Alafin
    Jul 7, 2017 at 10:18

2 Answers 2

Reset to default
7
$\begingroup$

It depends what your hash function is. If your hash function is the identity function, it's trivial to invert without constructing the hash table.

Your question seems to be essentially reinventing the idea of one-way functions. A one-way function is a function that can be computed in polynomial time but whose inverse cannot be. It is well known that the existence of one-way functions would imply that $\mathrm{P}\neq\mathrm{NP}$.

Improve this answer
$\endgroup$
1
$\begingroup$

If a problem has a polynomial reduction to another problem known to be in P then the problem is also in P.

The transformation from the problem of reversing the hash to hashtable lookup is not polynomial (generating all the entries). Which means you can't say anything about P-ness of the original problem.

The problem of reversing a hash is usually stated by giving as input the algorithm of the hash and an output of that algorithm. That is the actual problem.

Adding a hash table means spending exponential time to speed things up later. however from the perspective of the original problem statement it's still a $O(2^n + 1)$ algorithm.

As a comparison finding a wether a value is in an unordered array takes $O(n)$ time. You can sort the array in advance but that takes $O(n \log n)$ time but speeds up the actual finding operation down to $O(\log n)$ time. The end result is an algorithm that takes $O(n \log n + \log n) = O(n \log n)$ time.

Improve this answer
$\endgroup$
9
  • $\begingroup$ It's exponential. I am positing that the lower bound of reversing a hash is exponential--can this be proven? $\endgroup$
    – Tobi Alafin
    Jul 6, 2017 at 9:41
  • $\begingroup$ @TobiAlafin no because you can always create a hashtable from all possible inputs to the correct output. For example multiplying 2 numbers. Being able to do that says nothing about NP-ness of the problem $\endgroup$
    – ratchet freak
    Jul 6, 2017 at 9:50
  • $\begingroup$ Creating a hash table is exponential though? $\endgroup$
    – Tobi Alafin
    Jul 6, 2017 at 9:53
  • $\begingroup$ @TobiAlafin yes but that doesn't mean it's the only option for solving the problem. $\endgroup$
    – ratchet freak
    Jul 6, 2017 at 9:55
  • 1
    $\begingroup$ "Which means you can't say anything about P-ness of the original problem." Please read this sentence out loud in a very loud voice. Then consider rephrasing it. :-) $\endgroup$
    – David Richerby
    Jul 6, 2017 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.