Something that has been puzzling me for a while. When bloggers about theoretical computer science (TCS) talk about the status of the P vs. NP question, they always feel compelled to say something along the lines of "...but in practice thanks to the enormous power of modern SAT solvers (or ILP solvers, CP solvers etc) many NP-hard problems can be solved in reasonable time".
On one hand I understand why they write this; it is to emphasize that NP-hardness is by no means the end of the world. On the other hand, anybody who has used these tools will know that it is still fairly easy to build (structured) instances that are not too large and completely cripple them.
Is this lack of nuance in the discussion strategic (to really emphasize that NP-hardness is, in many real-world cases, only asymptotically a problem), or is it because the TCS community, in contrast to say the Operations Research community, knows about these tools but rarely makes use of them in practice and thus only has a limited understanding of their shortcomings?
Any thoughts?
=> More informations about this toot | More toots from skelk@mathstodon.xyz
@skelk Another couple of points I would like to integrate in the discussion
On one hand, my experience is that the connection between hardness in practice and NP-hardness is tenuous at best. SAT solver are fail on well known easy formulas regularly, simply because solvers employ generic algorithms and do not have the time to try specialized approaches that could win only few cases (we should remember that state-of-the-art SAT solvers live or die by SAT competitions).
The notion of "it works in practice" may sometimes be a self-fulfilling prophecy. SAT solvers are not used to break crypto because they do not work well there, still that's a very practical application. They are used mostly in application where it turns out they are fast. Moreover, expert encoders avoid well-known hard structures. For example, they avoid structures like the ones in pigeonhole principle because that is very hard for Resolution.
=> More informations about this toot | More toots from massimolauria@mathstodon.xyz
text/geminiThis content has been proxied by September (3851b).