I came across the example of the "bounded halted problem" recently, which I found quite intuitive for understanding P=NP https://www.lesswrong.com/posts/8Af3X8b

I came across the example of the "bounded halted problem" recently, which I found quite intuitive for understanding P=NP https://www.lesswrong.com/posts/8Af3X8b7f5piqtqZx/computability-and-complexity#Bounded_halting https://www.lesswrong.com/posts/8Af3X8b7f5piqtqZx/computabil... We're given a program P of length n, let's say it's a Turing machine with binary symbols on its tape. We want to know if P halts in fewer than n steps for all inputs. Notice that only the first n bits of those inputs are relevant (since it would take n+1 steps to reach the n+1th bit, by which time we'd know it hasn't halted in fewer than n steps). Hence we can answer this in exponential time: run P(000...) for n steps to see if it halts, run P(100...) for n steps, run P(010...) for n steps, etc. There are ~2ⁿ bitstrings of length < n, so it takes O(n × 2ⁿ) steps to check all inputs. This problem is in NP, since we can check a candidate input in polynomial time, e.g. checking `P takes at least n steps on the input 01010101` requires running P on that input for at most n steps. It's also NP-complete since we can translate other NP problems into it (see the link for details) The reason I like this example is that it gives an intuition for how "overpowered" a polynomial solution to it would be: able to infer seemingly-arbitrary information about any program, without having to actually run them. This is similar to how an oracle for the (usual) halting problem could be used to quickly prove/disprove arbitrary mathematical statements, just by feeding it a dumb, brute-force proof searcher. (Of course, we could state the same more directly, since theorem proving is itself NP-complete: checking a proof of size n is easy, but finding one seems to require exponential time; however, that seems more abstract than the running of a program on inputs)