CDR: Re: why should it be trusted?

[Riad S. Wahby]

Jordan Dimov <jdimov at 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 at mit.edu
MIT VI-2/A 2002

5105
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 1411 bytes
Desc: not available
URL: <https://lists.cpunks.org/pipermail/cypherpunks-legacy/attachments/20001017/9dea012d/attachment.sig>