<p>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 <a href="https://dl.acm.org/doi/10.1145/1667053.1667060" rel="nofollow noreferrer">Moser and Tordos</a>. 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.</p>
<p>PS: the answer to the 3-SAT problem may be provided by an oracle.</p>

CC BY-SA 4.0
2023-12-01T09:04:12.137Z
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.
Junqiang Peng
CC BY-SA 4.0
2023-12-01T09:16:10.177Z
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.
ironmanaudi
CC BY-SA 4.0
2023-12-01T11:07:03.910Z
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.
Emil Jeřábek
CC BY-SA 4.0
2023-12-08T23:16:48.063Z
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* https://en.wikipedia.org/wiki/Function_problem#Self-reducibility
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-12-09T02:12:54.323Z
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?
ndrwnaguib
CC BY-SA 4.0
2023-12-11T07:01:37.707Z
@ndrwnaguib Yes. This is what I meant. However, it seems like the answer is no in general according to Emil Jeřábek's answer. This is because if an efficient algorithm exists, one can utilize it to answer the decision problem by assuming the given k-CNF is satisfiable.
ironmanaudi
<np-hardness><np-complete><np>
Hardness for find the clause for statisfiable 3-SAT problems
ironmanaudi
# Hardness for find the clause for statisfiable 3-SAT problems

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

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](https://dl.acm.org/doi/10.1145/1667053.1667060). 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.

**Tags:** np-hardness, np-complete, np
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_3**: 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* https://en.wikipedia.org/wiki/Function_problem#Self-reducibility  
> **username_4**: 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?  
> **username_0**: @ndrwnaguib Yes. This is what I meant. However, it seems like the answer is no in general according to Emil Jeřábek's answer. This is because if an efficient algorithm exists, one can utilize it to answer the decision problem by assuming the given k-CNF is satisfiable.  

---

## 0 answers

