Graduate Research Forum Details
Representing Oracle Turing Machines as Satisfiability Instances
| Author: | Katrina Ray |
|---|---|
| Date: | April 10, 2007 |
| Time: | 16:00 |
| Location: | 220 Deschutes |
Abstract
One version of the satisfiability problem involves finding the lexicographically maximum satisfying (lex max sat) assignment for a given boolean formula. The decision version of this problem asks whether the lex max sat assignment is odd. This problem is the canonical Delta2-Complete problem. I will show that it is Delta2-Complete using a direct Cook-style reduction which demonstrates how to represent oracle turing machines using boolean formula.