Jordan Dimov <jdimov@cis.clarion.edu> wrote:
Probelms are not asymptotically Omega(N!) or Omega(N^N). Solutions are.
Nitpick if you will; you and I both know what the statement means, hence your ability to respond to it.
I don't believe anyone has ever proved that an NP-hard problem can not be solved in polynomial time.
"NP-hard ... a complexity class of problems that are intrinsically harder than those that can be solved by a nondeterministic Turing machine in polynomial time" (Algorithms and Theory of Computation Handbook, 19--20).
Not being able to solve a problem in polynomial time with current techniques does not make it unsolvable.
While I agree that the limitations of current techniques do not dictate what is possible, it _is_ possible to show that a certain problem has a best-case order of growth (for something simple, think of gate-level addition; its best case is provably Theta(log(N)) ). In this case, what Tim means is that work is being done towards showing that the best-case order of growth for factorization is faster than polynomial, hence it is NP-hard.
MIT people always surprise me.
Please, expound. -- Riad Wahby rsw@mit.edu MIT VI-2/A 2002 5105