함수 문제

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

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