Wout12345

Parker square P vs NP

May 20th, 2016
169
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.00 KB | None | 0 0
  1. We start from SAT:
  2.  
  3. There exists x1, x2, ..., x_n belonging to {true, false} so that F(x1, x2, ..., x_n)
  4.  
  5. with F(x1, x2, ..., x_n) being a Boolean formula (in conjunctive normal form). Equivalently, one could solve this problem:
  6.  
  7. There exists x1, x2, ..., x_n belonging to {true, false} so that not (not F(x1, x2, ..., x_n))
  8.  
  9. Define G(x1, x2, ..., x_n) as (not F(x1, x2, ..., x_n)).
  10.  
  11. There exists x1, x2, ..., x_n belonging to {true, false} so that not G(x1, x2, ..., x_n)
  12.  
  13. This statement is equivalent with the initial SAT problem. We can now write the formula G in conjunctive normal form as well, like any Boolean formula. We can now solve the problem using the following procedure:
  14.  
  15. 1) For each clause, do the following:
  16. 1.1) If the clause only contains variables or complements thereof, but never both of a single variable, this means we can assign the right values to these variables to make this clause false, and therefore the entire formula as well. This solves the problem, meaning that G can be "not satisfied".
  17. 1.2) If the clause contains both a variable and its complement, then the clause will be true under all circumstances. Move onto the next clause and repeat step 1.
  18. 2) If all clauses are passed without ever reaching step 1.1), this means each clause in the formula will always be satisfied. Therefore, the formula can not be "not satisfied".
  19.  
  20. This procedure can be completed in quadratic time per clause (perhaps even less, this is just using a naive algorithm). Therefore, the following problem can be solved in polynomial time:
  21.  
  22. There exists x1, x2, ..., x_n belonging to {true, false} so that not G(x1, x2, ..., x_n)
  23.  
  24. which, as stated earlier, is equivalent to the initial SAT problem:
  25.  
  26. There exists x1, x2, ..., x_n belonging to {true, false} so that F(x1, x2, ..., x_n)
  27.  
  28. In other words, the initial SAT problem can be solved in polynomial time as well. Since SAT is NP-complete, this means that P = NP.
  29.  
  30.  
  31.  
  32. That's the "proof". Good luck spotting the error, took me a bit of time personally. :P
Advertisement
Add Comment
Please, Sign In to add comment