Describe a Brute-Force Algorithm for Determining, Given a Compound Proposition$P$

Question

Examlex · Accepted Answer

The Answer is For each string of length

n

of the letters

\mathbf { T }

and

\mathbf { F }

(representing true and false), evaluate the given compound proposition when the

i ^ { ext {th } }

variable is assigned the truth value given by the

i ^ { ext {th } }

letter in the string. If any of these values of

P

is

\mathbf { T }

, then

P

is satisfiable; otherwise it is not. This will take at least

2 ^ { n }

steps in the worst case (the case in which

P

is not satisfiable), once for each such string. If

\mathrm { P } = \mathrm { NP }

, then there is a polynomial worst-case time algorithm, so the brute force algorithm is not the most efficient.

Describe a Brute-Force Algorithm for Determining, Given a Compound Proposition $P$