CDR: Re: why should it be trusted?

[Riad S. Wahby]

Jordan Dimov <jdimov at CIS.CLARION.EDU> wrote:
> Geee...  Since when are problems "proven" to be NP-hard??  Go back to your
> favorite undergrad institution and take a course on computational
> complexity again.  

Perhaps it is you who should do so.  Showing a problem to be
asymptotically Omega(N!) or Omega(N^N) (or Theta of either) is
effectively proving it to be NP-hard--that is, it grows in
non-polynomial time.

--
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: 899 bytes
Desc: not available
URL: <https://lists.cpunks.org/pipermail/cypherpunks-legacy/attachments/20001017/f997d542/attachment.sig>