Content deleted Content added
Chris-martin (talk | contribs) →As hard as an NP-complete problem: new section |
Chris-martin (talk | contribs) →As hard as an NP-complete problem: suggested replacement text |
||
Line 72:
:"This problem is at least as hard as the NP-complete longest path problem."
This seems like a very silly expression. Doesn't it just mean that the problem at least as hard as '''any''' NP-complete problem - which can be best stated by just calling it [[NP-hard]]? ~ [[User:Booyabazooka|Booya <sup>Bazooka</sup>]] 23:02, 4 October 2009 (UTC)
Perhaps what we should say is more along the lines of
:This problem is [[NP-hard]], which can be shown via a reduction to the [[longest path problem]].
~ [[User:Booyabazooka|Booya <sup>Bazooka</sup>]] 20:50, 5 October 2009 (UTC)
| |||