[FOM] Complexity of notions/intermediate degrees

[JoeShipman@aol.com]

Chow sayeth: 
>I don't think this quite satisfies your definition >of "intermediate" (with x = log m) but morally speaking it >seems to be intermediate.  But algorithms for factoring >continue to improve.



The best algorithms for factoring are not intermediate between polynomial and exponential in my sense.  Rather, they are functions with the property that for all n and all sufficiently large x, 
f(f(...n times...(f(x)))...) < 2^(2^(2^...(n times)))) < f(f(...n+1 times...f(x)...).

This might as well be exponential.  The "improvements" you speak of, as far as I am concerned, are trivial, except for the single time the exponent e was actually reduced from 1/2 (the original Morrison-Brillhart exponent from 1975) to 1/3 (Number field sieve of Lenstra, Pollard, Pomerance, and others from 1989).

The real issue is that the only natural building blocks we have to construct algorithmic functions from other algorithmic functions involve operators whose complexity is characterized by polynomials, exponentials, and logarithms.  So we can get a function whose log is a polynomial in the log of x, which isn't much better than polynomial in x, or a function which x is polynomial in the log of, which isn't much worse than exponential. 

The reason I think the shortage of natural intermediates is related to the difficulty of separating P from NP is that we don't have a computational operator of intermediate power (to separate P from EXP the strong operator of exponentiation was good enough).  If there were a natural intermediate function, one could construct a natural operator of intermediate power by using it to bound a search, which could lead to a whole in-between-realm of natural functions which are not in P and not NP-complete.  (If the true complexity of SAT is exponential, then factoring could be NP-complete but no function of "intermediate" complexity as I define it could be [at least for many-one reducibility, will need to think about the case of Turing reducibility]).

--Joe Shipman