>>14384614Yes, buckle up.
What the problem ultimately boils down to is finding contradictions in logical statements. For instance, A AND B OR C is not a contradiction because there exists a way for it to be true by assigning a value of true/false to each variable (in this case, you can set A = B = C = true). However, A AND (NOT A) is a contradiction because no matter what you set A to, you get true AND false, which is always false by the definition of AND (i.e. a contradiction). If any of this is confusing to you, read the basics on Boolean algebra.
Now, what does this have to do with P=NP and computation? Well, Boolean algebra is what is known as "universal", meaning all classical computation can be expressed as these basic logic functions. In fact, your CPU is just a bunch of switches that have been combined to make these basic logic gates, which have been combined to make more complex logic gates, etc. Look up nand2tetris if you're curious about the details.
You can think of a computer program as something that takes n bits (variables) as inputs and outputs z bits. Typically, 0 is false and 1 is true. One thing that would be very handy is the ability to find the inverse of a particular program in roughly as much time as it took you to run the program. That is to say, for a given program output, find *an* input to the program that will give you that output. You can express each output bit as a Boolean expression of the n input bits (variables), and then combine them into a single Boolean expression using AND and NOT. If a particular output bit is 1 then you simply AND that expression with the others, otherwise you AND its inverse (NOT) with the others. If you replace the variables in that final Boolean expression with true/false (0/1) you get either true/false as an output; that value tells you whether or not the input corresponds to the z-bit output you had before. Pause and make sure you understand this part.
cont.
