<p>hint: assign values to variables one at a time and call algorithm A on resulting formula. if the result of algorithm A is satisfiable or non-satisfiable what does that mean about last variable assignment?</p>

CC BY-SA 4.0
2023-12-31T00:39:09.153Z
2023-12-31T00:39:09.153Z
floating
<p>The problem: Given an algorithm A which can tell whether any 3CNF formula is satisfiable in poly-time, develop an algorithm B that calculates a solution for the formula, also in poly-time, using A as a sub-routine.</p>
<p>The only idea I have is to negate some literals (which we choose how?) and check again whether the (initially satisfiable) formula is still satisfiable - which would mean that the values of the negated literals are somehow &quot;essential&quot; in any valid solution. But this idea is way too vague, and maybe it is not the right direction at all.</p>
<p>Any hints and solutions are welcome!</p>

<complexity-classes><sat><np><boolean-formulas>
Solve 3CNF in Poly-Time with Satisfiability Oracle
Dilara
# Solve 3CNF in Poly-Time with Satisfiability Oracle

(Asked by: username_0 on 2023-12-30)

The problem: Given an algorithm A which can tell whether any 3CNF formula is satisfiable in poly-time, develop an algorithm B that calculates a solution for the formula, also in poly-time, using A as a sub-routine.

The only idea I have is to negate some literals (which we choose how?) and check again whether the (initially satisfiable) formula is still satisfiable - which would mean that the values of the negated literals are somehow "essential" in any valid solution. But this idea is way too vague, and maybe it is not the right direction at all.

Any hints and solutions are welcome!

**Tags:** complexity-classes, sat, np, boolean-formulas

---

## 1 answers

### Answer by username_1 on 2023-12-31. Score: 1 | Accepted answer

hint: assign values to variables one at a time and call algorithm A on resulting formula. if the result of algorithm A is satisfiable or non-satisfiable what does that mean about last variable assignment?


---

