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!


1 Answer 1


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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.