| ▲ | quibono 5 hours ago | |
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). | ||
| ▲ | mjdv 5 hours ago | parent | next [-] | |
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. | ||
| ▲ | tetha an hour ago | parent | prev | next [-] | |
Complexity theory has a couple of interesting "sandwiches" as a prof called them. For example, we know that LOGTIME is a subset of PTIME, which is a subset of NPTIME and PSPACE, both of which are a subset of EXPTIME. We also know that EXPTIME is strictly bigger than LOGTIME and PTIME. So somewhere between PTIME, NP, PSPACE and EXPTIME, there must be a change in computational capability. We just don't know where. This also exists between constant-depth circuit networks and algorithms using LOGSPACE. A circuit network of depth of log^2(input_size) can compute more than any nondeterministic LOGSPACE algorithm, which can compute more than a circuit network of constant depth using threshold gates. We also know that a deeper circuit network has strictly more computational power than the constant depth one. But where is the specific jump in computational power? We don't know. That makes the "practical applications" very strange to consider. I keep jesting, the funniest resolution of P vs NP would be that P = NP, except it has a cost factor that stops any practical collapse, like a proven minimum of O(n^<number of atoms in the universe>). That'd be the most annoying resolution of them all. | ||
| ▲ | emil-lp an hour ago | parent | prev [-] | |
If a problem is in NP, which all NP-complete problems are, then the yes-instances of the problem have "small" solutions that can be verified efficiently. Take sudoku. If I give you a difficult board, and also the solution, it is easy to verify that it is correct. Small efficient certificates do not exist for PSPACE-complete problems. Indeed for Sokoban, some instances require exponentially long sequences of pushes to solve. | ||