3 ms·
> 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 m
by Filligree 9y ago
> 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.
- deleted 9y ago[deleted]
- nl 9y agoThis 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.
- Filligree 9y agoWhich 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.