I find the 7/8-approximate algorithm for 3SAT to be simpler. Given a set of clauses C_1 ^ C_2 ^ ... ^ C_n where each clause is an OR of 3 logical variables, fi

I find the 7/8-approximate algorithm for 3SAT to be simpler. Given a set of clauses C_1 ^ C_2 ^ ... ^ C_n where each clause is an OR of 3 logical variables, find assignments to each variable to maximize the number of clauses satisfied. The algorithm is to just assign each variable randomly. For each clause, there are 8 possible assignments, and 7 out of 8 make the clause true. Therefore, randomly assigning them gives you a 7/8-approximation. What makes this so fascinating to me is that the difference between a (polynomial) algorithm that gets 7/8 right and one that gets 8/8 right is the difference between a child randomly guessing and solving all of the world's most important problems in a single algorithm. It could be worth trillions of dollars. Of course, it's probably impossible and therefore P != NP.