A polynomial-time algorithm for a promise problem that takes one of these constructs as input would imply “NP equals RP,” (-5[3])according to the Valiant–Vazirani theorem. The DPLL algorithm takes one of these constructs as input. (10[1]-5[3])In 1972, Richard Karp exhibited (-5[2])chains of polynomial-time (-5[1])reductions stemming from a problem taking one of these (-5[1])constructs (-5[2])as input, (10[1]-5[2])which was shown (-5[1])by the Cook–Levin (-5[1])theorem (10[1])to be NP-complete. (10[4]-5[3])These constructs (-5[1])can be placed in (-5[1])conjunctive normal (10[2]-5[1])form (10[2]-5[1])by applying (10[3]-5[1])De Morgan’s (-5[1])laws. (10[4]-5[6])These (10[1])constructs’ (10[2])clauses are restricted (-5[2])to contain (-5[1])at most (-5[1])three literals in a problem (10[1])abbreviated (-5[1])3SAT (-5[1])(“THREE-sat”), which (10[1])asks if there (10[1]-5[1])is an (10[1])input for which these constructs output (-5[1])“true.” (10[1]0[1]-5[4])For 10 (10[1])points, (-5[1])name these constructs built (10[1])by using (-5[1])operators (-5[1])like (-5[1])“AND” (10[1]0[1]-5[2])and (10[2]-5[4])“OR” (10[9]0[2]-5[5])to link (-5[1])variables (-5[3])that (-5[1])take (-5[2])the value (10[1]-5[1])true or (10[1])false. (10[2]0[2]-5[1])■END■ (10[23]0[39])