Tutorial on Computer Science for DNA Computers: Workshop on DNA Computers

Sunday Afternoon Tutorial on
Computer Science

3rd DIMACS Workshop on
DNA BASED COMPUTERS

Presenter: David Wood, University of Delaware

1935: Turing Defines "Effective Computational Procedure" To Be A Machine
- Turing's Starting Point was Talking About Computor Persons
  Algorithm = Turing Machine = "Effective Computational Procedure"
- Programmable Computers = Universal Turing Machine = Universal Computation
- Splicing Systems = DNA Turing Machine = Recombinant DNA Laboratory Techniques
Review of How Computational Complexity is Quantified
- Complexity Analysis Of Algorithms = How Much Time And Space?
  Example: Lookup in Telephone Directory, Find Path For HPP
- Complexity of a Problem = Complexity of Best Algorithm
- Problem Types: Decisions, Certificate, Inventories, And Optima
We Define "Checking Purported Solutions" To Be A Nondeterministic Machine
- Nondeterministic Algorithms Are Allowed Instruction CAREFULLY CHOOSE
  Example: Nondeterministic Algorithm For HPP
- Nondeterministic Computation = Nondeterministic Turing Machine = Checking A Purported Solution
- Not All Problems Have Solutions That Are Easy To Check
  Example: Winning N x N Checkers Game By Moving First
P Or Not NP, That Is The Question
- P (Polynomial) = Easy To Solve
  Example: Lookup In Telephone Directory
- NP (Nondeterministic Polynomial) = Easy To Check
  Examples: Anything In P, HPP, Protein Folding
- NP-Complete = 2000+ Equivalent, Hardest NP Problems
  - 1971: Cook Shows SAT Is The Hardest Problem In NP
  - The Class NP-Complete = All The Hardest Problems In NP
  - Polynomial Equivalence Is Impractical
- ``Is P = NP?'' Needs Only One Example
- Delicate Distinctions Between P and NP-Complete
- A O(2^q(n)) Upper Bound on NP-Complete Problems
Many Problems Are Harder Than NP-Complete (Lower Bounds of O(2^2^n))
- Winning N x N Checkers Game By Moving First (Game Theory)
- Quantifier Elimination (Logic)
- Cylindrical Algebraic Decomposition (Exact Polynomial Solutions)
- Gröbner Basis (Greatest Common Divisor and Gaussian Elimination -> Ideals in Rings)
- Pressburger Arithmetic (Number Theory)

This tutorial is from 1pm-3pm June 22.

Registration is free but limited.

Tutorials are held at the workshop location: John Morgan Building on the Hamilton Walk at the University of Pennsylvania, Philadelphia PA, in the "Class of '62 Lecture Hall," on the ground floor. Enter through the guard station at the east end of the Johnson Pavilion (shown on the same map).

The other Sunday afternoon (3pm-5pm) workshop is
June 22 Tutorial on Biolab Techniques for DNA Computers

Return to the homepage of the 3rd Annual DIMACS Workshop on DNA Based Computers

Email questions or comments to dna3-inquiry@cis.udel.edu.

Tutorial on Computer Science for DNA Computers: Workshop on DNA Computers
Compiled by / wood@cis.udel.edu / revised June 17, 1997