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

- Turing's Starting Point was Talking About Computor Persons
- 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

- Complexity Analysis Of Algorithms = How Much Time And Space?
- 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

- Nondeterministic Algorithms Are Allowed Instruction CAREFULLY CHOOSE
- 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

- 1971: Cook Shows
- ``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

- P (Polynomial) = Easy To Solve
- 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