Team:MoWestern Davidson/project mathmodel
From 2009.igem.org
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 * 22 = 12 clauses for 3 variables 2-SAT. There are 12C3 = 220 problems with 3 clauses. These are classified by their coarse distributions below.The table below gives the number of clauses satisfied for a few select 2-SAT problems for each input.
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.
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.