-
-
What is an algorithm?
-
-
-
Absolute Limitations on Algorithms
-
-
-
Resource limitations on algorithms
-
-
-
Divide and Conquer
-
Greedy
-
Landscapes
-
-
-
P versus NP
-
Building computers out of other problems
-
Unit Quiz
-
-
-
An algorithmic perspective on complex systems
-
-
-
Heuristics
-
Heuristics 2
-
Approximation algorithms
-
-
-
Randomized Algorithms I
-
Randomized Algorithms II
-
Randomized Algorithms III
-
Unit Quiz
-
-
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 , 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 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.)