"
Team:MoWestern Davidson/project mathmodel
From 2009.igem.org
(Difference between revisions)
(→Lego Models) |
(→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). | + | 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 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:Example.jpg]] | ||
| + | |||
| + | |||
{{Template:MoWestern_Davidson2009_end}} | {{Template:MoWestern_Davidson2009_end}} | ||
Revision as of 15:27, 27 July 2009
Lego Models
B2 Bomber
Rough and Fine distribution
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 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.
