Can you give me an example of any such problems (or a class of such problems)? By the definition of NP-complete, any problem in NP must be reducible to any problem in NP through a polynomial transformation.
On Jan 15, 2008 4:05 PM, Jim Bromer <[EMAIL PROTECTED]> wrote: > You're right. What I meant was that there are problems (not complexity > class decision problems) that can be defined as taking NP time (like O^n > time) and which would not be reducible to P-time even if the NP-Complete > Problems are. So even if NP-Complete problems can be solved in P-Time, you > will still have some problems that cannot be solved in P-Time. > Jim Bromer > > > > Robin Gane-McCalla <[EMAIL PROTECTED]> wrote: > Actually, SAT is an NP-complete problem > (http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#NP-completeness) > so if it were calculatable in polynomial time, then P = NP. > > > > > > > ________________________________ > Looking for last minute shopping deals? Find them fast with Yahoo! > Search.________________________________ > > This list is sponsored by AGIRI: http://www.agiri.org/email > To unsubscribe or change your options, please go to: > http://v2.listbox.com/member/?&; -- Robin Gane-McCalla YIM: Robin_Ganemccalla AIM: Robinganemccalla ----- This list is sponsored by AGIRI: http://www.agiri.org/email To unsubscribe or change your options, please go to: http://v2.listbox.com/member/?member_id=8660244&id_secret=86285197-f1da0c
