A decision problem is called decidable when:

Options

  • A. It has no possible solution
  • B. It can be solved only in exponential time
  • C. An algorithm always terminates with the correct Yes or No answer
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

C. An algorithm always terminates with the correct Yes or No answer

Detailed Explanation

  • Decidable Problem: A decision problem for which an algorithm exists that produces the correct answer and halts on every valid input.
  • Output: Yes or No.
  • Example: Checking whether a given integer is even or odd.
  • Remember: A decidable problem does not necessarily have to be solvable in polynomial time.
← Previous Next →

Attempt Quiz Now:

TRE 4 Theory of computations Practice set 1

Feature Posts