 Suggested languages for you:

Europe

Problem 19

# Define the unique-sat problem to be $$U S A T=\\{\langle\phi\rangle \mid \phi$$ is a Boolean formula that has a single satisfying assignment $$\\}$$. Show that $$U S A T \in \mathrm{P}^{S A T}$$.

Expert verified
To show that $$USAT \in P^{SAT}$$, we presented a polynomial-time algorithm that uses a SAT oracle to solve the USAT problem in three steps. Step 1 checks if the given Boolean formula $$\phi$$ is satisfiable using the SAT oracle. In Step 2, we iteratively query the oracle to find a satisfying assignment for $$\phi$$. In Step 3, we submit a new formula $$\psi$$ to the oracle to check if there's a second satisfying assignment. If no second assignment exists, we conclude that $$\phi$$ has a unique satisfying assignment and thus belongs to $$USAT$$. The algorithm makes O(n) oracle calls, thus establishing that $$USAT \in P^{SAT}$$.
See the step by step solution

## Step 1: Check if the formula is satisfiable

Firstly, we need to check if the given Boolean formula $$\phi$$ is satisfiable or not. We can simply do this by submitting the formula $$\phi$$ to the $$SAT$$ oracle. If the oracle returns "unsatisfiable", we know that $$\phi$$ has no satisfying assignments, and thus it cannot belong to $$USAT$$.

## Step 2: Find a satisfying assignment

If the oracle returns "satisfiable", we know that there is at least one satisfying assignment for $$\phi$$. To find that assignment, we can iteratively query the $$SAT$$ oracle for each variable $$x_i$$ in the formula $$\phi$$. For example, we could submit the formula $$(\phi \wedge x_1)$$ to the oracle. If the oracle returns "satisfiable", it indicates that there is a satisfying assignment where $$x_1$$ is true. If the oracle returns "unsatisfiable", it means the satisfying assignment must have $$x_1$$ set to false, and we can submit $$(\phi \wedge \overline{x_1})$$ as the new query. We can repeat this process for all variables in the formula, and after n queries, we will have a complete satisfying assignment for $$\phi$$ (where n is the number of variables in $$\phi$$).

## Step 3: Check for a second satisfying assignment

To ensure that $$\phi$$ has only one satisfying assignment, we need to check if there is another satisfying assignment that is different from the one we found in Step 2. We can do this by submitting a new formula $$\psi$$ to the $$SAT$$ oracle, where $$\psi = (\phi \wedge \overline{s})$$, where $$s$$ represents the complete satisfying assignment we found in Step 2 (with $$\overline{s}$$ being the negation of the entire assignment). If the oracle returns "unsatisfiable", it means there is no other satisfying assignment different from $$s$$, and we can conclude that the given formula $$\phi$$ has a unique satisfying assignment, and therefore belongs to $$USAT$$. If the oracle returns "satisfiable", it indicates that there is at least one more satisfying assignment, and thus $$\phi$$ is not in $$USAT$$. In the worst case, the presented algorithm makes 1 initial query plus n queries for finding the satisfying assignment plus 1 additional query to check for a second satisfying assignment. Therefore, it runs in O(n) oracle calls, which corresponds to a polynomial-time complexity. As we have shown an algorithm that solves the $$USAT$$ problem using a $$SAT$$ oracle in polynomial time, we conclude that $$USAT \in P^{SAT}$$.

We value your feedback to improve our textbook solutions.

## Access millions of textbook solutions in one place

• Access over 3 million high quality textbook solutions
• Access our popular flashcard, quiz, mock-exam and notes features ## Join over 22 million students in learning with our Vaia App

The first learning app that truly has everything you need to ace your exams in one place.

• Flashcards & Quizzes
• AI Study Assistant
• Smart Note-Taking
• Mock-Exams
• Study Planner 