3 ms·
I recently became interested about P=NP, the reason was learning. And I became crankish, in the sense of trying to understand the problem myself. My advice is
by js8 8y ago
I recently became interested about P=NP, the reason was learning. And I became crankish, in the sense of trying to understand the problem myself.
My advice is - learn about naturalness. Monotone circuit bound in CLIQUE in particular is an interesting result, which knocks out many straightforward approaches to show that P=NP. The Wigderson recent book gives a very good overview.
However, I wish in some sense this was better explained, that there was more examples of algorithms that cannot work because they can be, in some sense, represented as monotone circuits.