Simon took a piece of paper and drew P vs. NP and other complexity classes. P vs. NP is probably the most famous millennium problem, one of the seven most important open questions in mathematics (and computer science). Solving such a problem can get you a million-dollar prize from the Clay Mathematics Institute Millennium Prize Problems and, much more importantly, help the humanity understand the fabric of the universe a bit better. Simon has been showing an on and off interest in the P vs. NP problem for a while, but it’s the first time I saw him place P and NP in a larger context. Put very simply, the big question is whether P equals NP, that is whether all problems which can be verified quickly can also be solved quickly. Obviously, NP contains P, but is it also true the other way around? Or in Simon’s words:
P is all that can be solved in polynomial time (amount of time that grows in a polynomial way with the size of the input). NP are the problems that may or may not be solved easily but if you have a solution, you can check it easily. The other complexity classes are:
L (LogSpace) – problems that can be solved in logarithmic memory.
NL (NLogSpace) – problems that can be verified in logarithmic memory.
PSpace – problems that can be solved in polynomial memory.
ExpTime – problems that can be solved in exponential time.
ExpSpace – problems that can be solved in exponential memory.
Now, here’s the crazy thing: we don’t know if L = NL, or if NL = P, or if P = NP, or if NP = PSpace, or if PSpace = ExpTime, or if ExpTime = ExpSpace! We do know some things, though, like that P does not equal ExpTime (we have problems, like playing chess, which we know are in ExpTime, but not in P. We can’t use chess to prove that P does not equal NP though, because if I give you a move in chess, it will be really hard to check if it’s the optimal move).
We have also had a very interesting discussion about the difference between a fallacy and a paradox. Simon has explained to me that a paradox is something that is true but counterintuitive (we thought one good example would be Heisenberg’s uncertainty principle). Contrary to a paradox, something that is impossible (like a proof that 1 equals 2, I’m sure you’ve seen one of those in this blog 🙂 ) is a fallacy.
Suppose you have a good argument leading to an absurd statement. If you find a flaw in the argument, then you have a fallacy. If you notice that the statement is true after all, on the other hand, then you have a paradox.
These have been inspired by Simon’s new hero Undefined Behavior and his old hero Primer.
Geeks out of the box 