# IF satisfiability problem belonged to P, can the certificate be found efficiently?

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

• 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.
– plop
Mar 9 at 15:50
• 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) Mar 9 at 15:59
• 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.
– plop
Mar 9 at 16:01
• 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.
– plop
Mar 9 at 16:05
• Does this answer your question? Is finding a solution of a satisfiability problem harder than deciding satisfiability? Mar 9 at 18:26