Skills101
← All practice quizzes

Quiz: Decidability and Complexity

5 questionsNo time limitPass: 60%+10 XP on first pass

The limits of computation: decidable and undecidable problems, the halting problem proof (with a Python-style paradox), reductions, Rice's theorem, then complexity — P, NP, NP-complete, NP-hard, SAT and why P vs NP matters — with a brute-force SAT solver and verifier in Python.

Log in to take the quiz

Free account · see your score, answers and explanations, earn XP

  1. Question 1

    Why can no program decide the halting problem?

  2. Question 2

    What does "NP" stand for?

  3. Question 3

    If someone found a polynomial-time algorithm for SAT, what would follow?

  4. Question 4

    Rice's theorem says which of these is undecidable in general?

  5. Question 5

    In the SAT demo, how many assignments might brute force need for n = 20 variables?