Only need to do question (c)

Problem 1 The complexity class DP is defined as follows: DP={ languages L: there is a language L1NP and a language L2coNP such that L=L1L2.} (An equivalent definition is that L is in DP if and only if L=A\B for two languages A,BNP, i.e. L is the set-theoretic difference of two languages in NP.) (a) Define the language ALMOST-SAT to be the language of all CNF formulas which (i) are unsatisfiable, but (ii) would become satisfiable if any clause were removed. Show that ALMOSTSAT is in DP. (b) Now define the language ONE-SAT to be the set of all Boolean formulas such that has exactly one satisfying assignment. Show that ONE-SAT is in DP. (c) Give a characterization of DP in terms of deterministic polynomial-time algorithms equipped with a SAT oracle. Justify your characterization. As an example of what a characterization of a different complexity class (our friend NP) would look like in terms of polynomial-time algorithms equipped with a SAT oracle, here is such a characterization for NP: a language is in NP if and only if it is decided by a deterministic polynomial-time algorithm that makes one SAT oracle call and accepts if and only if the call accepts. (The notion of "non-adaptivity" may be useful: an oracle algorithm is non-adaptive if it makes all of its calls to the oracle "in parallel" (i.e. all the strings on which the oracle is every queried are selected before the oracle is ever called - the choice of the i-th of those strings doesn't depend on what the oracle answered on the first i1 calls)