0
$\begingroup$

IF SAT(satisfiability problem) belongs to P, then is it possible for a certificate of an arbitrary instance of SAT to be found efficiently?

$\endgroup$
7
  • 1
    $\begingroup$ You can go variable by variable. Give the first variable the value False and run the algorithm on the resulting formula. If the resulting formula is satisfiable keep that variable with that value and move to the next variable. If not, then give the variable the value True and move to the next variable. Do the same with subsequence variables. $\endgroup$
    – plop
    Mar 9 at 15:50
  • $\begingroup$ i thought because it is already a member of P, verifying it will be easy(done efficiently). so if the verification is done efficiently, then finding the certificate will also be easy(done efficiently) $\endgroup$
    – Mikey
    Mar 9 at 15:59
  • $\begingroup$ Well, the procedure above only repeats the algorithm (which is assumed to run in polynomial time) as many times as the number of variables in the formula. $\endgroup$
    – plop
    Mar 9 at 16:01
  • 1
    $\begingroup$ The argument above shows it only for this particular problem. Then if you have any other problem that can be efficiently reduced to SAT, incidentally it shows it for those as well. $\endgroup$
    – plop
    Mar 9 at 16:05
  • 2
    $\begingroup$ Does this answer your question? Is finding a solution of a satisfiability problem harder than deciding satisfiability? $\endgroup$
    – Kyle Jones
    Mar 9 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.