17 Oct
2000
17 Oct
'00
9:56 p.m.
Jordan Dimov <jdimov@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@mit.edu MIT VI-2/A 2002 5105