1
$\begingroup$

The 3-SAT problems are known to be NP-complete so the decision problems are believed to be non efficiently solvable unless P=NP. Yet, there are cases where the satisfiability can be answered such as the condition given by the Lovasz local lemma (LLL). When the LLL is met, it is suggested that a feasible assignment to the variables can be found efficiently and an exemplified polynomial time algorithm is first proposed by Moser and Tordos. Therefore, my question is does knowing the answer to the decision problem (i.e., 3-SAT) help lower the complexity of the corresponding searching problem (i.e., finding the satisfiable assignment)? Or, on the other hand, the problem is still NP-hard.

PS: the answer to the 3-SAT problem may be provided by an oracle.

$\endgroup$
6
  • 2
    $\begingroup$ I don't know if this is what you want. If you have an oracle to answer the decision version of 3-SAT, then you can find a satisfiable assignment by calling this oracle polynomial times. The idea is that you can guess a variable, say $x$, to be true or false, and then ask the answer to the restricted formula. If setting $x$ to true makes the restricted formula still satisfiable, then you keep $x$ to be true and then repeat this process on the restricted formula until all variables are decided. $\endgroup$ Dec 1, 2023 at 9:04
  • $\begingroup$ Thanks for the reply. The oracle mentioned in the question may be misleading. My question is: given a satisfiable 3-SAT problem, can an assignment be efficiently found? Or, it is NP-hard to find the assignment even if one knows that the problem is satisfiable. $\endgroup$ Dec 1, 2023 at 9:16
  • 3
    $\begingroup$ Any efficient algorithm to this problem can be used to efficiently decide satisfiability. Given a 3-CNF $\phi$, run the algorithm on $\phi$ (even if it may be unsatisfiable). If it outputs a satisfying assignment, output YES, if anything else happens, output NO. If $\phi$ is satisfiable, the algorithm finds a satisfying assignment as promised. If it is not, the algorithm may crash, or compute garbage, but whatever it does, it will not output a satisfying assignment as none exists. $\endgroup$ Dec 1, 2023 at 11:07
  • 1
    $\begingroup$ Just to give the keyword, the property of SAT that makes it possible to reduce the search problem to the decision problem is called self-reducibility en.wikipedia.org/wiki/Function_problem#Self-reducibility $\endgroup$
    – a3nm
    Dec 8, 2023 at 23:16
  • $\begingroup$ From your reply to @JunqiangPeng, I am assuming that you are only allowing a single query to the oracle. Then, is the question whether this valuable information would help to efficiently solve this particular instance? $\endgroup$
    – ndrwnaguib
    Dec 9, 2023 at 2:12

0

Your Answer

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

Browse other questions tagged or ask your own question.