Complexity Explorer Santa Few Institute

Introduction to Computation Theory

Enroll

Lead instructor:

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

5.3 Unit Quiz » Quiz Explanation

1) If you take a brute-force algorithm for max-flow, and then come up with a better algorithm, does this show P = NP? 

No - P versus NP is a question about all brute-force search algorithms, not any particular one.

 

2) If you improve a brute-force search algorithm for an $\mathsf{NP}$-complete problem, such as Kidney Donor Matching, to take polynomial time instead, this would show $\mathsf{P}=\mathsf{NP}$.

True - NP-complete problems are formally the hardest problems in NP, and a polynomial-time solution for any one NP-complete problem would yield a polynomial-time algorithm for all problems in NP.

 

3) The Halting problem is NP-complete.

Although one can "build a computer'' using the Halting problem---indeed, the question itself is about the behavior of computers---NP-completeness only applies to problems that are in $\mathsf{NP}$, by definition. Every problem in $\mathsf{NP}$ can be solved by a brute-force algorithm, so is necessarily computable, but the Halting problem is uncomputable, so it is not in $\mathsf{NP}$. (Problems that are at least as hard as any problem in $\mathsf{NP}$ are called "$\mathsf{NP}$-hard'', which is 'half' of $\mathsf{NP}$-completeness.)

 

4) NP-completeness has nothing to do with geometry.

False - In the video we saw that a natural tiling problem, which is very geometric, is $\mathsf{NP}$-complete. (Geometry also enters into $$\mathsf{NP}$-completeness in many other ways, e.g. through linear optimization problems and through an advanced research program called Geometric Complexity Theory, which reasons about computational complexity using geometry.) In fact, there are few areas of mathematics that are not touched on by $\mathsf{NP}$-completeness.