Remix.run Logo
▲ mjdv 5 hours ago

It's difficult to give any strong answers. Since there's no proof that NP != PSPACE, we don't actually concretely know what the difference between the classes is, and the plain assumption that NP != PSPACE doesn't tell you where to look.

I am also not an expert on complexity theory.

But intuitively: if you try to work with these two types of problems, you find that NP-complete problems are way more amenable to _pretty good_ solutions. There are very effective SAT solvers out there, and ILP solvers. Finding a TSP solution on almost any graph on tens of thousands of nodes is quite easy, and making good adversarial instances is hard. There are many programming challenges around NP-complete problems online that attract effective solvers, e.g. PACE, and previously [:(] Google Hashcode. PSPACE-complete problems on the other hand feel really, really intractable, where even solving small instances is very difficult, and I think the article we're commenting on gives a good feeling for that.