Team:MoWestern Davidson/project mathmodel

From 2009.igem.org

(Difference between revisions)
(→Rough and Fine distribution)
(→Rough and Fine distribution)
Line 7: Line 7:
-
SAT problems (satisfiability problems) are logic decision problems that ask if a combination of true-false variables (inputs) can be assigned to make the expression true.  Here, we are using 3 variables: a, b, and c.  For each variable there are 2 literals, either  primed (a’) or unprimed (a).  ).  A clause is two literals connected with OR, hence 2-SAT.  A SAT problem is a set of clauses connected with AND.
+
To classify SAT problems, we began looking at the Rough distribution of each problem, meaning how many inputs  satisfied a certain number of clauses in a problem. The table below gives the number of clauses satisfied for a few select 2-SAT problems for each input.  
-
 
+
-
To classify SAT problems, we began looking at the Rough distribution of each problem, meaning how many clauses were satisfied by each input. The table below gives the number of clauses satisfied for a few select 2-SAT problems for each input.  
+
[[Image:1.JPG‎]]
[[Image:1.JPG‎]]
 +
 +
 +
Fine distributions look deeper at how each clause was satisfied, either singly or doubly. If an input satisfies one or two literals in a clause, that clause is satisfied singly or doubly respectively. Here is a example of fine distribution using the  problem from the table above.
 +
 +
{{Template:MoWestern_Davidson2009_end}}
{{Template:MoWestern_Davidson2009_end}}

Revision as of 16:00, 27 July 2009

Lego Models

B2 Bomber

Rough and Fine distribution

To classify SAT problems, we began looking at the Rough distribution of each problem, meaning how many inputs satisfied a certain number of clauses in a problem. The table below gives the number of clauses satisfied for a few select 2-SAT problems for each input.


1.JPG 


Fine distributions look deeper at how each clause was satisfied, either singly or doubly. If an input satisfies one or two literals in a clause, that clause is satisfied singly or doubly respectively. Here is a example of fine distribution using the  problem from the table above.



Retrieved from "http://2009.igem.org/Team:MoWestern_Davidson/project_mathmodel"