logoalt Hacker News

quibono • today at 9:43 AM • 1 reply • view on HN

I've always struggled to understand what the difference is. Is PSPACE-completeness "worse" in a practical sense?

I'm assuming P != NP (and NP != PSPACE).


Replies

mjdv • today at 10:05 AM

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.