함수 문제

계산 복잡도 이론에서 함수 문제란 판정 문제가 아닌 문제들, 다시 말해서 답이 예/아니오보다 복잡한 문제들이다. 이를테면, 외판원 문제나 소인수 분해 문제는 답이 인수의 목록으로 나온다. 일반적으로 함수 문제는 판정 문제보다 다루기 힘들다.

함수 문제도 판정 문제와 같은 방식으로 복잡도 종류를 나눌 수 있다. FP는 결정론적 튜링 기계가 다항 시간에 풀 수 있는 함수 문제의 집합이고, FNP는 비결정론적 튜링 기계가 다항 시간에 풀 수 있는 함수 문제의 집합이다.

같이 보기

• 결정 문제
• 최적화 문제