Complexity Explorer Santa Fe Institute

Your progress is not being saved! Enroll now or log in to track your progress or submit homework.

Introduction to Computation Theory

Lead instructor:


7.1 Heuristics » Quiz Explanation

1) If you come across a hard computational problem that you can solve by brute force, one good strategy is to reduce it to SAT and then use an off-the-shelf SAT-solver.

True  -This is often, though not always, a good strategy. If the problem can be solved by brute force then it is (likely) in $\mathsf{NP}$, so it can be reduced to SAT. SAT-solvers have been very well-developed and are often highly efficient in practice, even though it has been proved that they are not efficient on all possible inputs. The same can be said for CLIQUE-finders, Integer Linear Programming, and solving systems of polynomial equations.

 

2) Even though SAT-solvers are often very ecient in practice, this does not show P = NP.

True - To show $\mathsf{P}=\mathsf{NP}$ requires an algorithm that works in polynomial time on \emph{all} inputs. The practical efficiency of most SAT solvers today relies on the fact that instances that occur in practice are often \emph{not} worst-case inputs. In fact, for most modern SAT solvers, it has even been proved rigorously that there exist instances on which they take exponential time. (It's just that these instances don't frequently arise in practice.)