Home › Quizzes › Computability and Complexity

Computability and Complexity

This quiz covers the fundamental concepts of Computability and Complexity, including Turing machines, computability, complexity classes, and algorithms.

14 Questions Published
Play Quiz Practise this topic out loud

Questions

Question 1 Multiple Choice (Single Answer)

What is the halting problem?

  1. The problem of determining whether a given program will terminate or run forever.
  2. The problem of determining the time complexity of a given program.
  3. The problem of determining the space complexity of a given program.
  4. The problem of determining the correctness of a given program.
Question 2 Multiple Choice (Single Answer)

What is a Turing machine?

  1. A mathematical model of a computer.
  2. A physical computer.
  3. A programming language.
  4. A software application.
Question 3 Multiple Choice (Single Answer)

What is computability?

  1. The study of what can be computed by a Turing machine.
  2. The study of the efficiency of algorithms.
  3. The study of the correctness of programs.
  4. The study of the security of computer systems.
Question 4 Multiple Choice (Single Answer)

What is a complexity class?

  1. A set of problems that can be solved by a Turing machine in a certain amount of time.
  2. A set of problems that can be solved by a Turing machine in a certain amount of space.
  3. A set of problems that can be solved by a Turing machine in a certain number of steps.
  4. A set of problems that can be solved by a Turing machine in a certain amount of memory.
Question 5 Multiple Choice (Single Answer)

What is the P complexity class?

  1. The class of problems that can be solved by a Turing machine in polynomial time.
  2. The class of problems that can be solved by a Turing machine in exponential time.
  3. The class of problems that can be solved by a Turing machine in linear time.
  4. The class of problems that can be solved by a Turing machine in logarithmic time.
Question 6 Multiple Choice (Single Answer)

What is the NP complexity class?

  1. The class of problems that can be solved by a Turing machine in nondeterministic polynomial time.
  2. The class of problems that can be solved by a Turing machine in deterministic polynomial time.
  3. The class of problems that can be solved by a Turing machine in exponential time.
  4. The class of problems that can be solved by a Turing machine in linear time.
Question 7 Multiple Choice (Single Answer)

What is the relationship between P and NP?

  1. P = NP.
  2. P != NP.
  3. P is a subset of NP.
  4. NP is a subset of P.
Question 8 Multiple Choice (Single Answer)

What is an algorithm?

  1. A set of instructions for solving a problem.
  2. A computer program.
  3. A mathematical proof.
  4. A data structure.
Question 9 Multiple Choice (Single Answer)

What is the time complexity of an algorithm?

  1. The amount of time it takes the algorithm to run on a given input.
  2. The number of steps it takes the algorithm to run on a given input.
  3. The amount of memory it takes the algorithm to run on a given input.
  4. The number of instructions it takes the algorithm to run on a given input.
Question 10 Multiple Choice (Single Answer)

What is the space complexity of an algorithm?

  1. The amount of time it takes the algorithm to run on a given input.
  2. The number of steps it takes the algorithm to run on a given input.
  3. The amount of memory it takes the algorithm to run on a given input.
  4. The number of instructions it takes the algorithm to run on a given input.
Question 11 Multiple Choice (Single Answer)

What is the difference between a deterministic and a nondeterministic algorithm?

  1. A deterministic algorithm always takes the same path through the program, while a nondeterministic algorithm can take different paths.
  2. A deterministic algorithm always terminates, while a nondeterministic algorithm may not terminate.
  3. A deterministic algorithm uses less memory than a nondeterministic algorithm.
  4. A deterministic algorithm is always more efficient than a nondeterministic algorithm.
Question 12 Multiple Choice (Single Answer)

What is a reduction?

  1. A way of transforming one problem into another.
  2. A way of proving that two problems are equivalent.
  3. A way of finding a solution to a problem.
  4. A way of analyzing the efficiency of an algorithm.
Question 13 Multiple Choice (Single Answer)

What is the Cook-Levin theorem?

  1. A theorem that states that SAT is NP-complete.
  2. A theorem that states that P = NP.
  3. A theorem that states that NP is a subset of P.
  4. A theorem that states that P is a subset of NP.
Question 14 Multiple Choice (Single Answer)

What are NP-complete problems?

  1. Problems that can be solved by a Turing machine in polynomial time.
  2. Problems that can be solved by a Turing machine in exponential time.
  3. Problems that can be reduced to SAT.
  4. Problems that are at least as hard as SAT.
← Back to Quizzes