patternMajor
Is SAT an existential question?
Viewed 0 times
satquestionexistential
Problem
Some sources state that an algorithm that solves the SAT problem not only needs to decide whether a given existentially-quantified formula is satisfiable or not, but, additionally, in the case where the formula is satisfiable, it does need to provide a satisfying assignment. Is this true or not?
I am bit confused, since I thought the SAT problem would just be an existential question.
I am bit confused, since I thought the SAT problem would just be an existential question.
Solution
The SAT problem is a decision problem. It means that an algorithm that solves SAT must answer
However, as many decision problems, there is a functional problem associated to SAT, that asks to find a satisfying assignment when there exists one.
There is a polynomial time reduction from the functional problem to the decision problem. Check here to see what it looks like.
true or false, and not necessarily find a satisfying assignment.However, as many decision problems, there is a functional problem associated to SAT, that asks to find a satisfying assignment when there exists one.
There is a polynomial time reduction from the functional problem to the decision problem. Check here to see what it looks like.
Context
StackExchange Computer Science Q#154722, answer score: 22
Revisions (0)
No revisions yet.