Consider a proposition of n variables. Here is an algorithm for checking for satisfiability: Generate a...

Transcribed Image Text:

Consider a proposition of n variables. Here is an algorithm for checking for satisfiability: Generate a truth table for the proposition. Check if all lines of the truth table are false. If not, the proposition is satisfiable. Why is this algorithm exponentially costly? Consider a proposition of n variables. Here is an algorithm for checking for satisfiability: Generate a truth table for the proposition. Check if all lines of the truth table are false. If not, the proposition is satisfiable. Why is this algorithm exponentially costly?