
Applied Math Applied Math Forum 
 LinkBack  Thread Tools  Display Modes 
May 4th, 2013, 01:19 AM  #1 
Senior Member Joined: Jan 2013 Posts: 209 Thanks: 3  P equals NP because 3SAT reduces to solving linear equations
3SAT is a set of constraints on n boolean vars. Each constraint is on 3 vars and excludes 1 of 8 combinations of them each being true or false. Create an undirected network of size 8*n*(n1)*(n2)/6 with 8 nodes for each set of 3 different boolean vars. Thats a group of 8 nodes for each set of 3 different vars. Divide by 6 since theres 6 ways to order 3 things. Each node is defined as 3 specific boolean values for its vars. There is a node for each possibility. An edge between a pair of nodes means none of the var values they specify contradict the values in the other node. In each group of 8 nodes, there is no edge between any of them. Only 1 can be true at a time. This is the normal math found in a bayesian node of 3 vars. Its 8 weights sum to 1. Between each pair of nodes that have 2 vars in common (if 3 there is no edge), there is an edge if all the common vars have the same boolean value, else there is not an edge. Between each pair of nodes that have 1 var in common, there is an edge. It does not matter if the var value contradicts because edges between nodes that have 2 vars in common do all the work. Between each pair of nodes that have no vars in common, there is an edge. If the 3SAT constraints are solvable, then the Max Clique in the 8*n*(n1)*(n2)/6 nodes is size n*(n1)*(n2)/6, else it would be smaller. I'm writing the rest of this proof assuming that Max Clique is there, because if its not we'll find out when the set of linear equations have no solution. For each 3SAT constraint, we know a certain node is not in the clique. Its the node that refers to the 3 boolean vars of the constraint and the specific true/false values of them which the constraint excludes. Each 3SAT constraint excludes 1 of 8 possibilities, like setting a bayesian weight to 0 and leaving the other 7 (or less if multiple constraints refer to the same 3 vars) required to sum to 1 in some combination. The size n*(n1)*(n2)/6 clique contains 1 node from each group of 8 nodes. It contains no other nodes. Each group of up to 8 nodes is an anticlique, has no edges, so I already have Clique Cover which is in NP, but it gets simpler than that as linear equations. I'm going to reduce 3SAT to a set of linear equations that must all be solved simultaneously. Create n*(n1)*(n2)/6 scalar vars which range 0 to 1 as probabilities, 1 for each node. For each of the groups of 8 nodes defined above (the anticliques), add a Linear Equation: sum of those 8 scalars = 1 For each 3SAT constraint, add a Linear Equation: thatConstraintsNode = 0 For each anticlique, for each 2 of its 3 vars, for each of 4 possibilities of the 2 vars (each are true or false), [ There are 2 nodes w and x in that anticlique which are this specific possibility. for each of n3 other vars, [ There are 2 other nodes which agree on the values of those 2 common vars. One node (y) thinks the value is true. The other (z) thinks its false. Add a Linear Equation that means the chance of the 2 common vars being these specific values in this anticlique equals the same thing in the other anticlique: w + x = y + z This translates Bayes Rule across anticliques 3 vars at a time because each of w, x, y, and z refer to specific values of their 3 boolean vars. That's why they call it 3SAT. Like NAND is a constraint on 3 bits (2 in and 1 out), 3 is the minimum for Turing Completeness (computers are made of NAND logic) and its finite version and subset: NP. ] ] Any set of values of the scalar vars (1 for each node) which do not solve the equations violates Bayes Rule on some combination of 4 vars, between which there are 32 nodes which communicate with eachother through the "w + x = y + z" equations which refer to 2 of 8 bayesian weights on each side. The scalar vars are bayesian weights. But is it enough to solve the Linear Equations? Does that prove 3SAT constraints are satsified by the boolean values agreed on by the remaining n*(n1)*(n2)/6 nodes? It does if the equations exactly define all the information in all the 3SAT constraints, because there would be nothing else to solve. "thatConstraintsNode = 0" excludes the specific 3 boolean var values that each constraint excludes. There can be 0 to 8 constraints on each 3 vars, all affecting nodes in the same anticlique. "sum of those 8 scalars = 1" makes each 3 vars have only 1 combination of 3 boolean values, or a total probability of 1 for a mix of them as Bayes Rule handles exactly. In other words, it can't at any time think "x and not x". This defines the relationship between constraints in the same anticlique. "w + x = y + z" defines the only relation left between combinations of constraints across different anticliques. Bayes Rule is a fact of statistics: chance(x, given y) * chance(y) = chance(y, given x) * chance(x) If I flip 2 coins and tell you at least 1 landed heads, whats the chance both landed heads? Most people says 1/2 or 1/4, but there are 4 ways 2 coins can land, I excluded 1 of those 4, then I asked what is the chance of 1 of the 3 remaining possibilities. It is Human intuition to choose 1 coin to say is certainly heads, since we know "at least 1 landed heads", and then to think about the other coin separately, but that is wrong. You can't say the dime landed heads, and you can't say the nickel landed heads. All you can say is at least 1 of the dime and nickel landed heads. It could be (dime heads, nickel tails), (dime tails, nickel heads), or (dime heads, nickel heads). Like they say about quantum physics, observing a specific possibility changes the outcome. if you know the nickel is heads, the chance both are heads is 1/2, but if you only know at least 1 of 2 coins is heads, the chance is 1/3. This mistake most people make causes a misunderstanding of the combination of any 2 events, a problem in Human intuition so deep it makes people think things like 3SAT are hard to solve even with the help of a computer. All the information in 3SAT is exactly translated to a set of linear equations that implement Bayes Rule, therefore solving those equations is solving 3SAT. Since solving linear equations is in P, and 3SAT is interchangible with all NP math problems, P equals NP. Those who would challenge this proof should do so by telling which information in 3SAT constraints is not exactly translated to the set of linear equations or by disproving the exactness of Bayes Rule on combinations of boolean vars. If Bayes Rule works so well, then why isn't it already used for 3SAT? Because its normally used in acyclic networks. My network has cycles to the point of being a clique, and not just any clique, a clique of anticliques covering all nodes in which there is a clique of nodes if the 3SAT constraints are solvable. 
May 4th, 2013, 01:55 AM  #2 
Senior Member Joined: Jan 2013 Posts: 209 Thanks: 3  Re: P equals NP because 3SAT reduces to solving linear equat
EDIT: n*(n1)*(n2)/6 scalar vars should be 8*n*(n1)*(n2)/6 scalar vars, same as number of nodes.

May 4th, 2013, 03:51 AM  #3 
Senior Member Joined: Jan 2013 Posts: 209 Thanks: 3  Re: P equals NP because 3SAT reduces to solving linear equat
Or to say it a simpler way, sumsToOne(set of probability vars) constraint is in NP because it can represent bayesian nodes, NAND, Rule 110, and 3SAT as sumsToOne constraints on combinations of their 3way conditional vars, in some cases the opposite set of conditionals with the same set on another side. sumsToOne is in NP, and sumsToOne is a linear equation.... x + y + z ... = 1. Since bayesian weights translate to squared vars in quantum math which also sums to 1, sumsToOne in that context is the equation of a unit hypersphere. Can you make all the hyperspheres have radius 1 simultaneously, even though they share some perpendicular dimensions but not others? Or lets keep it simple... All of computing theory reduces to the sumsToOne constraint. Rule 110 moves down to second place as simplest universal math operator for containing at least the 8 bits of data in its name. sumsToOne is in the laws of physics. All probability amplitudes must sum to 1.

May 4th, 2013, 12:51 PM  #4 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: P equals NP because 3SAT reduces to solving linear equat
Solving systems of integer equations is not known or believed to be in P.

May 22nd, 2013, 06:54 PM  #5 
Senior Member Joined: Jan 2013 Posts: 209 Thanks: 3  Re: P equals NP because 3SAT reduces to solving linear equat
I was afraid of that, but it looked so simple at the time. I guess we just have one more translation, which at least looks easier to solve.


Tags 
3sat, equals, equations, linear, reduces, solving 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Solving a system of linear equations  sparrow  Linear Algebra  2  September 21st, 2013 07:51 PM 
Solving A System Of Linear Equations  soulrain  Linear Algebra  2  January 19th, 2013 07:32 AM 
Solving System of NonLinear Equations  guitardude89  Applied Math  1  May 14th, 2012 02:31 AM 
Solving NonLinear equations  amira_63  Complex Analysis  3  November 16th, 2010 07:41 AM 
Solving linear equations  where have I gone wrong?  anonymoose  Linear Algebra  1  January 14th, 2010 11:46 AM 