3 ms·
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 t
by lacker 7y ago
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.