부분합 문제

정수 여러 개와 목표값 T 가 주어질 때, 그 가운데 일부를 골라 합이 정확히 T 가 되게 할 수 있는지 묻는다(부분집합 합 문제라고도 한다). 고른 수들을 받으면 더해 보기만 하면 되므로 NP 에 속하고, NP-완전이다. 수가 n 개면 고르는 방법은 2ⁿ 가지다. 표를 채워 가는 동적 계획법으로 n·T 에 비례하는 시간에 풀 수 있지만, T 를 적는 자릿수로 재면 지수 시간이어서 다항 시간 알고리즘은 아니다(이런 것을 유사 다항 시간이라 한다).