News for hackers. Stuff that matters.

A comment on The Scientific Case for P≠NP. Parent comment

Re:The Scientific Case for P≠NP by Filligree on Sunday October 29, 2017 @09:38AM (#15579232)
> Maybe it is untrue but it is possible to define the set of cases where it is untrue. If this is the case, it seems likely that class is very small, so it is mostly true. That is the opposite of a proof of course, but it does seem reasonable to think about your confidence of it being true as being somewhat proportional to the likely size of the class.

Any NP-complete problem reduces to any other, so if P=NP for any of them then it's true in general. Some more efficiently than others, of course.

[ Parent | on HN ]
Re:The Scientific Case for P≠NP by nl on Sunday October 29, 2017 @11:12AM (#15579583)
This is a fair point.

I guess my only response would be that some of the complexity classes in "some more efficiently than others, of course" might be impractical even if they are theoretically possible.

[ Parent | on HN ]
Re:The Scientific Case for P≠NP by Filligree on Sunday October 29, 2017 @11:50AM (#15579731)
Which might be the saving grace should the equality turn out to be true, given the sheer number of scary-powerful algorithms that happen to be NP-complete. Certainly it'd be convenient if they were solvable, but... probably not safe, you understand?

Not really relevant here, though.

[ Parent | on HN ]