# Last edited on 2014-10-03 17:58:01 by stolfilocal
# NOT POSTED
# Reply to @TheFascistMind (old @AnonyMint)

[quote author=TheFascistMind link=topic=789978.msg9060430#msg9060430 date=1412296426]
You also didn't see the point of complexity theory.
[/quote]

Continuind my earlier post:

I emphasize that this is an academic discussion that has no practical consequence except to show that theory has nothing to say on the robustness of SHA256.

Two theoretical fields were used in your post: the theory of complexity classes (P, NP and all that) and big-O analysis.  Neither can be applied to SHA256.

First, both theories only apply to problems where the size [i]n[/i] of the input is variable and unbounded; and they consider what happens[i] in the limit when [i]n[/i] tends to infinity[/i].  If [i]n[/i] is bounded, no matter how big, all the definitions collapse and [i]every[/i] problem is not only polynomial, but can be solved in O(1) time.  

In fact, if you cannot let [i]n[/i] go to infinity, strictly speaking you cannot even apply the definitions; you get barred at the door.  

But suppose you generalize the problem in such a way that the input size [i]n[/i] can go to infinity, and you can analyze its complexity as "polynomial" or "exponential" or "O(n^2)".   Still, these results will not say anything about the cost for any specific [i]n[/i], such as [i]n[/i] = 256 bits.  

You cannot tell whether an algorithm runs in O(1) time or requires exponential time by looking at what it does forany finite set of inputs; and vice-versa.   

One can easily define two algorthms A0 and B0 such that A0 runs in O(1) time, B0 runs in exponential time, A0 and B0 give the same output for every input with size [i]n[/i] below 10[sup]500[/sup].  One can easily define two functions F0 and G0, where F0 can be computed in O(1) time while G0 requires exponential time, but such that F0(x) = G0(x) for every input x whose size n is less than 10[sup]500[/sup].  These are trivial exercises, that do not require any arguments or ideas more complicated than the definitions. 

In a previous post you told how replacing an O([i]n[/i]^k) algorithm by an O(log [i]n[/i]) one made a huge difference in running time.  I have a few such success stories myself. (Back in 1979, when working as a part-time programer for an egineering firm, I saved a large govt-funded project by substituting an O(1) table lookup for an O([i]n[/i]) search in a COBOL program, with [i]n[/i] about 1000, after even the COBOL experts from IBM Brazil had failed to make the program run fast enough.  I never again got so much praise in my life.  :D)

However, justifying those successes in terms of asymptotic (big-O) analysis or P-vs-NP is wrong, because that kind of analysis does not actually let you conclude anything about the actual running time on a specific application.  It is like the explanation of the successful businessman in the old joke at the end of [url=https://bitcointalk.org/index.php?topic=740394.msg8640299#msg8640299]this post[/url].

Your wrote:
[quote author=TheFascistMind link=topic=789978.msg9039523#msg9039523 date=1412155135]
The [url=http://www.princeton.edu/~achaney/tmve/wiki100k/docs/Polynomial_time.html]definition of polynomial time[/url] is precisely the time complexity class [i]O(n[sup]k[/sup])[/i].

The relevance is that for NP complexity class, very small increases in [i]n[/i] causes exponential (not polynomial) increases in computation cost.

If the best known inversions of SHA256 are NP, then NP is relevant because it means there is some smallish value of [i]n[/i] for which no inversion is practical. Afaics, this is what complexity theory gains us.
[/quote]

The first sentence is correct, the other two are dead wrong. 

First, a formal nit:  the class NP contains P, and no one knows whether NP is equal to P or not. Therefore, proving that something is in NP does not prove that it is not P, and even proving that it is "NP-complete" (which is what people usually mean when they lazily say just "NP") does not prove that it is not P.   

Also another nit: there are many classes of asymptotic complexities between "polynomial" and "exponential", so "not polynomial" includes for example algorithms that run in O([i]n[/i] [sup]log log log log [i]n[/i])[/sup] time, which for some problems would be very interesting indeed.  

The terms "exponential" and "polynomial" can be applied to the [i]increase[/i] in running time only when they can be applied to the running time itself; that is, if there is a problem size variable [i]n[/i] that can grow without bounds.  And, even then, they describe how the cost increases when [i]n[/i] tends to infinity.  I repeat: those terms are meaningless if the size [i]n[/i] is bounded (and doubly so if [i]n[/i] is fixed).

It is a terrible misconception to think that "exponential cost" is bigger (or grows faster) than "polynomial cost".  That is true only for "sufficiently large [i]n[/i]", but the theory does not say when [i]n[/i] is "sufficiently large"; it could be true only for [i]n[/i] greater than 10[sup]500[/sup].  See the example algorithms A0 and B0 aboe, and the functions F0 and G0 above.  There is [b]nothing[/b] in the theory that justifies saying that the breakpoint is "smallish".

You may object that examples like F and G are contrived and unreal.  But my statement remains correct even if the costs grow smoothly with [i]n[/i], according to some simple formulas.  Suppose that algorithm A1 finishes after 10[sup]200[/sup]×[i]n[/i] operations, algorithm B1 finishes after 10×[i]n[/i][sup]50[/sup] operations, and algorithm C1 finishes after 10×1.00000000000001[sup][i]n[/i][/sup] operation, all three formulas being exact (up to rounding) and valid for all inputs.  By the definitions, A1 runs in polynomial, O([i]n[/i]) time; B1 is polynomial too, with O([i]n[/i]50) time; nd C1 is exponential.  According to the "polynomial good, exponential bad" mantra, algorithm A1 should be better than B1, which should be better than C1.  However, plug [i]n[/i] = 1000 in those formulas, and you get exactly the opposite order -- and only C1 will be fast enough to use.  

There are some very important real problems where the algorithms with best asymptotic complexity lose in practice to algorithms that in theory are much worse.   I recall that, perhaps 10 years ago, two students in India found a polynomial-time algorithm to decide whether a number is composite.  At the time, their algorithm ran in O([i]n[/i] 14) time, where [i]n[/i] is the number of bits in the input.  (It may have been improved since then, I haven't checked.)  It was a great result for the theory; but, for the sizes [i]n[/i] that are relevant to cryptography, their algorithm was much slower than the super-polynmial algorithms that crypto people were using.

The Closest Point Problem (CPP) is like this: given a fixed set [i]S[/i] of [i]sites[/i] (points) in a square, and then a series of [i]query[/i] points, find for each query [i]q[/i] the site [i]p[/i] in [i]S[/i] that is nearest to [i]q[/i].  One efficient solution is to set [i]S[/i] create a quad-tree from the

Strictly by the definitions, the "Bitcoin Mining Problem" (BMP), the partial inversion of SHA256, is O(1), because it does not matter what the algorithm outputs when [i]n[/i] is not 256.  Hence, strictly by the definitions, BMP is in P, and therefore is in NP; but is not NP-complete.