Size of the solution space isn't the right word. I mean the function of the size changes from exponential (
nk) to polynomial (
nO(1)).
If it is possible to convert the computation time (resource cost) from an exponential function of to a polynomial function of the inputs of the algorithm, then the complexity has been reduced from NP to P.
I cited a link which I believe demonstrated this, although I may be mistaken.
The search space for brute force inversion of SHA256 is
2bits, e.g. a 128-bit hash has
2128 possible outputs. All known methods for inverting SHA256 are NP relative to
bits, and often cryptanalysis attacks remain in NP and only reduce the exponent by a factor that makes them practical solve for certain
n. For example for finding collisions, the
birthday attack is
2bits/2. However, some attacks may reduce the complexity to P, e.g. a quantum computer (Shor's algorithm) on RSA reduces integer factorization from sub-exponential to polynomial.
NP requires that the solution can be verified in polynomial time. For example, the verification that the input to a hash produces a certain output.
Please feel free to correct me if I am still wrong.
It is not an error of fact, but only the use of a theory that is not really relevant to the problem.
All you wrote is correct, but, as you note, NP and P (and the
O() notation) are meaningful only if the number of bits
n is considered variable, and they describe how the cost grows
ultimately as
n goes to infinity (informally, "just before
n reaches infinity"). The theory has nothing to say if one considers a specific
n (say, 256), or any
n less than some fixed bound, (say,
n up to 1 million bits). In that case, the complexity classes cannot be distinguished: every function with a finite domain can be computed in polynomial time, indeed in
O(1) operations. This is a trivial observation that follows directly from the definitions.
So, even if inverting a generalized
n-bit version of SHA were to be proved to be superpolynomial with respect to
n, that would not say anything about the difficulty of inverting SHA256 for 128 or 256 bits -- which is what matters. There may even be an algorithm, out there in the vast unexplored depths of the algorithm jungle, that can be implemented in practice and solves the Bitcoin Mining Puzzle -- for
n = 256, specifically -- with less operations than it takes to compute the two rounds of SHA256. (Needless to say, most cryptographers are betting their careers that there is no algorithm that is fast enough to be of practical use, much less one
that fast.)
It is unfortunate that complexity theorists still teach computer science students that their theory has practical relevance, to the point of using the word "efficient" as synonym of "polynomial time". In fact, that theory is as relevant to software development as
the Banach-Tarsky paradox is to manufacturing.
