Can we solve a 3-SAT problem with supressor logic?

From GcatWiki
Revision as of 15:12, 4 April 2009 by Eckdahl (talk | contribs) (How could suppressor logic be used to solve the Sakamoto 3-SAT problem?)
Jump to: navigation, search

What is the 3-SAT problem?

How did Sakamoto et al. use a DNA computer to solve a 3-SAT problem?

Sakamoto et al.

What is suppressor logic?

How could suppressor logic be used to solve the Sakamoto 3-SAT problem?

Definitions

Inputs = framshift suppressor tRNAs

Input value = supp a is 1, supp g is 0; supp b is 1, supp h is 0, etc. up to tth 6th pair of f and l

Logical clause (LC) = three inputs connected by OR, eg. (a OR b OR e)

Logical expression (LE) = string of LCs connected by AND

Subroutine

1. Individual bacteral cells use Hin/hix system to randomly choose of of the 64 possible combinations of 6 inputs.

2. Each bacterial cell carries out the following subroutine on each LC: IF LC=TRUE THEN "check the next LC" ELSEIF LC=FALSE "go get a new set of inputs with step 1"

3. If/when a bacterial cell finds a set of inputs that satisfies the entire LE (ie. a solution to the 3-SAT problem), it will glow green.