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.