HiveBrain v1.2.0
Get Started
← Back to all entries
patternMajor

Is SAT an existential question?

Submitted by: @import:stackexchange-cs··
0
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.

Solution

The SAT problem is a decision problem. It means that an algorithm that solves SAT must answer 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.