Hacker News Reader

Comment by joe_the_user | Hacker News Reader

My pure amateur, possibly muddled understanding is that P=!NP is rather different from most open conjectures.

A) It's extremely general or even "foundational" in the sense that it's asking whether any algorithm at all exists to solve an extremely general sort of problem in polynomial time.

B) All of the standard methods used to solve problems of this sort have at least been pronounced exhausted at this point.

C) Very few theorems that inherently limit the speed of a class of problems actually have ever been proven. Very few methods for proving these constraints are known.

D) A lot of famous theorems have yielded results through being embedded in a larger, different field where they are just one result of many proved with a new machinery (Fermet most prominently). But given P=!NP is so general it can't really embedded in a larger, tractible space - lots of things are equivalent to it but all these things are kind of the same.

View on HN

Great post. Here are a few things pointers if you want more information about your points:

B) The situation is actually worse than exhausted. We know (have proven) that the regular methods simply won't work (check up "the reletaivzation barrier" and "natural proofs" and "algebrization")

C) We actually can construct problems which take at least a certain amount of time to solve (though admittedly many of them are kind of unnatural). Search up "time hierarchy theorem". This is probably one of the theorems you mention. However, you're right, as far as natural problems go, it appears to be extreme difficult to prove most natural problems takes at least linear time (https://mathoverflow.net/questions/4953/super-linear-time-co...). Note the log*... factor grows extremely slowly.

In fact, it is not known whether SAT requires more than linear time. Since SAT is NP-complete, we expect it to have no polynomial time algorithm... and yet here we are wondering whether it requires even more than linear time. If you are interested in this sort of thing, maybe look up fine-grained complexity. Also note that to solve P != NP, we will have to atleast shown P != PSPACE, since PSPACE contains NP. However, even this seemingly easier problem has had no progress and seems like it would require a huge breakthrough.

>>B) The situation is actually worse than exhausted. We know (have proven) that the regular methods simply won't work (check up "the reletaivzation barrier" and "natural proofs" and "algebrization")

I've heard of those, even tried to read the proof. Still, my understanding is those claims are ultimately "informal proofs" despite having formal step so the situation isn't entirely closed-up but still very bad.

Maybe this will help with understand the revitalization barrier. Most proof of separations of complexity classes relativize, in that not only do they show

A strict subset B

they also show

A^O strict subset B^O

for ANY oracle O. Most of these proofs don't actually explicitly state this is true, but they are readily to be extended this way (e.g. the diagonlizing proofs of the time hierarchy theorem)

However, we know (Baker, Gill, Solovay) that there exists and oracle O1 where

P^O1 subset NP^O1

as well as an oracle O2 such that

P^O2 not subset NP^O2

Therefore, we know we a proof of P != NP must not relativize or else that would contradict the aforementioned result.

P^O is always a subset of NP^O, whatever the O.

I think the gp left out the strict before the later subset statements.

That's right! I completely flubbed that part while doing some other edits! Thanks. What I wanted to say is there are O1 and O2 such that:

P^O1 strict subset NP^O1

and

P^O2 equals NP^O2

From this it seems that the question itself might have been hopelessly naive

Is there any evidence that P might be equal to NP? This seems different from other famous conjectures like Fermat's Last Theorem or Riemann's Theorem where what's hard is finding a counterexample that disproves the theory.

I think RJ Lipton (blog author) and Knuth believe it could be true. However, most complexity theorists don't (I think Fortnow does a survey of theorists on this every few years). Knuth says something like "well all it would take is a single algorithm for any of these hundreds of problems". A fine take for the godfather of algorithms. At the same time, there are many people who have in some sense tried to find such an algorithm, even non-explicitly (e.g. factoring would be in P if P = NP). Moreover, there is a lot of complexity theoretic work which makes it hard to believe it to be true (I think Scott Aaronson's blog has some presentable information about this)

http://www.informit.com/articles/article.aspx?p=2213858&WT.m...

Note that Knuth does not believe that the constant factor on the P algorithm be will be less than the size of the entire Universe.

On the first P algorithm found, or any P algorithm?

It isn’t that different - most complexity theory conjectures are this way.

Basically, there are all these classes of algorithm. P can be solved in polynomial time, NP can be solved in polynomial time by a computer that gets really lucky with rng, PSPACE can be solved with polynomial space, L can be solved in logarithmic space. For many of these pairs, it kinda feels like they are not the same, but we can’t prove it.

So in particular we don’t know that P != PSPACE, which is a much weaker statement, and a very similar one, compared to P != NP.

Similarly, we can’t prove there are cryptographically secure hash functions, and we can’t prove it’s hard to factor numbers.

Basically, we just have very few mathematical tools for proving that complexity classes are different. It’s hard to prove that algorithmic problems are hard. We have diagonalization, which shows that the halting problem is impossible and that P != EXPTIME, and that’s about it.

Anyway, I would conclude not that P != NP is a uniquely hard problem, as much as that complexity theory is very young compared to most fields of mathematics, and there are still many statements we can’t prove.

P vs NP is also distinguished in that many people think it has profound philosophical implications. Nick Land seems to think this (http://www.uf-blog.net/crypto-current-021/), and so does Scott Aaronson (“if P=NP, the word would be a profoundly different place than we usually assume it to be ... there would be no value in “creative gaps””). Though I think Land’s idea is a lot more interesting — he says P vs NP is a paraphrase of the analytic vs synthetic distinction.

Reply on news.ycombinator.com