Question

Let S be a set of n distinct positive integers, and let t be a positive integer. Devise an algorithm that determines, with O(nt) operations in the worst-case, if there exists a subset of S whose elements total t. Just because you can find an algorithm that runs in O(nt) time doesn’t mean that subset-sum is polynomial. Why not?

Answer 1

The Subset-Sum problem is considered to be NP-complete and does not have a polynomial-time algorithm with a worst-case time complexity of O(nt).

Step-by-step explanation:

The Subset-Sum problem is an example of a problem that is considered to be NP-complete. This means that there is no known polynomial-time algorithm that solves it with a worst-case time complexity of O(nt). Although an algorithm with a time complexity of O(nt) may exist for some instances of the problem, this does not make the problem itself polynomial, as there are instances of the problem that require exponentially more operations.

The Subset-Sum problem asks whether there is a subset of a given set of integers whose sum is equal to a target value. It is a decision problem, meaning that the algorithm only needs to determine whether such a subset exists or not.

To truly determine if Subset-Sum is polynomial, one would need to prove that there exists an algorithm that can solve all instances of the problem with a worst-case time complexity that is a polynomial function of the size of the input. Thus far, no such algorithm has been discovered.