Pseudo code for algorithm

profileunicorn13

You are given a magical "oracle" which van correctly solves the CIRCUIT-SAT problem in polynomial time-- i.e., for a given circuit the oracle will return a 1 if and only if the circuit is satisfiable; it returns 0 otherwise. 

The catch is that the oracle does not give you a satisfying truth assignment if the circuit is indeed satisfiable

Describe a poly-time algorithm (which uses the oracle as a subroutine) constructing a satisfying truth assignment for a given circuit ( in the event that is indeed satisfiable)

    • 9 years ago
    • 20
    Answer(0)