Which of the following problems is known to be NP-Complete?

Options

  • A. Subset Sum Problem
  • B. Sorting an array
  • C. Finding the maximum element in an array
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

A. Subset Sum Problem

Detailed Explanation

Subset Sum is a classic NP-Complete problem. Given a set of integers and a target value, its decision version asks whether some subset of the numbers has a sum exactly equal to the target. A proposed subset can be checked efficiently, so the problem belongs to NP. Subset Sum is also NP-hard. Although dynamic programming can solve many practical instances efficiently with respect to the numeric target, its traditional complexity is pseudo-polynomial, not polynomial in the input bit length.
← Previous Next →

Attempt Quiz Now:

BPSC TRE 4 DSA Practice set 1

Feature Posts