Hacker News Reader

Comment by justifier | Hacker News Reader

Richard Karp: (Berkeley, unsure, P!=NP) My intuitive belief is that P is unequal to NP, but the only supporting arguments I can offer are the failure of all efforts to place specific NP-complete problems in P by constructing polynomial-time algorithms.

I believe that the traditional proof techniques will not suffice. Something entirely novel will be required.

My hunch is that the problem will be solved by a young researcher who is not encumbered by too much conventional wisdom about how to attack the problem.

View on HN

>> My intuitive belief is that P is unequal to NP, but the only supporting arguments I can offer are the failure of all efforts to place specific NP-complete problems in P by constructing polynomial-time algorithms.

Actually, there has been tremendous incremental progress in inventing better and better algorithms for NP Complete problems. As a result, these problems are more deeply understood now. I think that the gap to poly time is closing fast.

Contrast that with the almost complete absence of progress in proving P != NP.

Also, from a practical viewpoint, many NP Complete problems of industrial size are now solved routinely.

Sure, in some cases (the easy ones) we can solve NP-complete problems. However, tons of useful instances of NP-complete problems are not particularly close to being solved. We can even characterize fairly well when the instances become hard (for instance, for graph problems the treewidth seems relevant). I see absolutely no evidence that we're anywhere close to constructing a polynomial-time algorithm for any NP-complete problem. If anything, we are slowly finally making some progress on proving P != NP because we are finally getting some nontrivial superlinear bounds on these problems (thus far, the biggest obstacle to proving P != NP has been the difficulty of proving anything about lower bounds on runtime that isn't directly tied to space consumption).

Seriously, if you're interested in this approach ("well, in practice we can solve the problem if [insert thing here] is bounded"), check out the field of parameterized complexity. It's very popular in the database area. It also reveals some very sharp limits to tractability for these problems in practice, not just in theory.

>> (thus far, the biggest obstacle to proving P != NP has been the difficulty of proving anything about lower bounds on runtime that isn't directly tied to space consumption)

I probably don't understand the proofs of these bounds - it seems to me though, that any lower bound without some relationship to the time or space to input the problem into some kind of computer, implies a belief that an instance might be solvable in-place, in some physical system.

I have some doubts about that ....

To be clearer, a trivial lower bound is something like "the input is of size n and for any n-1 length yes-instance you can find n-length extensions that are no-instances, so you have to check all n elements." It doesn't tell us anything interesting about the worst-case problem complexity. What's been surprising is how hard it is to make meaningful lower-bound statements stronger than that (well, not surprising to people who work on this stuff for a living, I guess). But that doesn't make it more likely that P = NP, really, except in the sense that we (obviously) haven't characterized the entire space of problems in P yet.

To more specifically address your "in-place" concerns, you can often formulate the problem in terms of circuit complexity--circuits are inherently parallel, so minimum circuit depth is a good proxy for a required number of steps, and it's also generally agreed that if you can design a circuit to do something it's physically realizable (even though that's arguably not always true, especially in cases with very wide fanout). So a (somewhat) promising direction has been to try to find circuit complexity lower bounds for problems, especially nontrivial ones.

>> complete absence of progress in proving P != NP

We've ruled out a number of techniques and also have shown that any solution must fall into a category avoiding a number of conditions (natural proof, algebrization barrier). Note also Ryan Williams' result separating ACC0 and NEXP. All of that is progress as I see it.

It's simply that construction of practical approximation algorithms or heuristics that work on large instance is (in general) much easier than separating proofs for complexity classes.

>> It's simply that construction of practical approximation algorithms or heuristics that work on large instance is (in general) much easier than separating proofs for complexity classes.

I agree, but the search for better algorithms is also more principled. At some point, separating complexity classes looks like counting the number of angels on a pinhead. It's probably interesting in an abstract way for some people - but it's not my cup of tea, as they say.

It's true that there has been a lot of practical progress and even theoretical progress, though often of the form "we improve 1.8^n running time to 1.65^n". But...

> As a result, these problems are more deeply understood now. I think that the gap to poly time is closing fast.

I'd disagree. As we develop more and more understanding of these problems, we still are only improving exponentials to other exponentials (in theory - practice may be different) and so we remain in a fundamental sense as far away from polynomial-time solutions as ever, despite improved understanding.

NP hardness is defined in terms of worst-case hardness, not average case hardness. As long as there exists even one instance that makes your algorithm take non-polynomial amount of time to terminate, P won't be equal to NP.

That's why I'm becoming increasingly skeptical of the usefulness (in the scientific sense) of complexity theory as it's currently laid out. We already know that instances of NP-Hard problems are either easily solvable, in poly-time, or take exponential time, depending on the location of the instance in the problem space.

For example in SAT, the distance of the instance to the critical clause/variable threshold. In subset sum, the density of the instance.

It's not the problem class that matters.

Well, even if it was, it may not be communicable to those speaking a different language.

Reply on news.ycombinator.com