Re:The World's Simplest Interesting Algorithm (2019)
by throw149102 on Wednesday June 10, 2020 @02:17AM
(#23474466)
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.
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.