Representing Oracle Turing Machines as Satisfiability Instances


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.

Structure-Shy Programming Revisited


Adaptive Programming (AP), developed as an extension to OO in the 90s, separates the concern of where to navigate on objects (WHERE-TO-GO) from the concern of what to do during the navigation (WHAT-TO-DO). The history-based navigation abstractions provided by AP allow modifications to the underlying object topology without affecting its associated computation. We call such programs structure-shy because they withstand some changes to the underlying data-structure.


Subscribe to RSS - Colloquium