Team:MoWestern Davidson/project mathmodel

From 2009.igem.org

(Difference between revisions)
(Rough and Fine distribution)
(Rough and Fine distribution)
Line 19: Line 19:
The rough distribution for the red problem is '''0143'''. That distribution means 0 inputs satisfied 0 clauses, 1 input satisfied 1 clause, 4 inputs satisfied 2 clauses and 3 inputs satisfied all 3 clauses.
The rough distribution for the red problem is '''0143'''. That distribution means 0 inputs satisfied 0 clauses, 1 input satisfied 1 clause, 4 inputs satisfied 2 clauses and 3 inputs satisfied all 3 clauses.
 +
 +
The following pie chart shows 2-SAT 3-clause problems grouped by rough distribution.
Line 25: Line 27:
[[Image:Superspecialawesome.png|none|750px]]
[[Image:Superspecialawesome.png|none|750px]]
-
 
-
 
-
 
'''Fine distributions''' look more deeply at how each clause was satisfied. If an input satisfies one or two literals in a clause, that clause is satisfied '''singly''' or '''doubly''' respectively. For example, the input abc’ satisfies the clause  (a OR b’) singly because only a from the input is in the clause.  However, the same input abc’ satisfies the clause (b OR c’) doubly because both b and c’ are in the input and clause.
'''Fine distributions''' look more deeply at how each clause was satisfied. If an input satisfies one or two literals in a clause, that clause is satisfied '''singly''' or '''doubly''' respectively. For example, the input abc’ satisfies the clause  (a OR b’) singly because only a from the input is in the clause.  However, the same input abc’ satisfies the clause (b OR c’) doubly because both b and c’ are in the input and clause.

Revision as of 21:12, 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. There are 3C2 * 2^2 = 12 clauses for 3 variables 2-SAT. There are 12C3 = 220 problems with 3 clauses. The table below gives the number of clauses satisfied by each input for a few select 2-SAT problems.



Table2.png



The rough distribution for the red problem is 0143. That distribution means 0 inputs satisfied 0 clauses, 1 input satisfied 1 clause, 4 inputs satisfied 2 clauses and 3 inputs satisfied all 3 clauses.

The following pie chart shows 2-SAT 3-clause problems grouped by rough distribution.



Superspecialawesome.png

Fine distributions look more deeply at how each clause was satisfied. If an input satisfies one or two literals in a clause, that clause is satisfied singly or doubly respectively. For example, the input abc’ satisfies the clause (a OR b’) singly because only a from the input is in the clause. However, the same input abc’ satisfies the clause (b OR c’) doubly because both b and c’ are in the input and clause.

The fine distribution for the red problem from the table above is 0011212100. This distribution means that 0 inputs satisfied 0 clauses, 0 inputs satisfied 1 clause singly, 1 input satisfied 1 clause doubly, 1 input satisfied 2 clauses with 2 singles, 2 inputs satisfied 2 clauses with 1 single and 1 double, 1 input satisfied 2 clauses with 2 doubles, 2 inputs satisfied 3 clauses with 3 singles, 1 input satisfied 3 clauses with 2 singles and 1 double, 0 inputs satisfied 3 clauses with 1 single and 2 doubles, and 0 inputs satisfied 3 clauses with 3 doubles.


Picture5.png