My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
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*(n-1)*(n-2)/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*(n-1)*(n-2)/6 nodes is size n*(n-1)*(n-2)/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*(n-1)*(n-2)/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*(n-1)*(n-2)/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 n-3 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*(n-1)*(n-2)/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.
BenFRayfield is offline  
 
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*(n-1)*(n-2)/6 scalar vars should be 8*n*(n-1)*(n-2)/6 scalar vars, same as number of nodes.
BenFRayfield is offline  
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 3-way 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.
BenFRayfield is offline  
May 4th, 2013, 12:51 PM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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.
BenFRayfield is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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 Non-Linear Equations guitardude89 Applied Math 1 May 14th, 2012 02:31 AM
Solving Non-Linear 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





Copyright © 2018 My Math Forum. All rights reserved.