함수 문제

계산 복잡성 이론에서 함수 문제는 모든 입력에 대해 하나의 출력(전체 함수의 출력)이 기대되는 연산 문제지만, 결정 문제의 출력보다 출력이 더 복잡하다.기능 문제의 경우 출력은 단순히 '예'나 '아니오'가 아니다.

형식 정의

기능 문제 $P{\displaystyle }$ ${\displaystyle P}$은(는) 임의의 $알파벳{\displaystyle \mathrm{}}$ {$${\$displaystyle \Sigma}$ 문자열에 대한$$ $R{\displaystyle }$ ${\displaystyle$ R$}($으)로 정의된다$.$

${\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}.}$

알고리즘이 $모든{\displaystyle }$ $입력{\displaystyle }$ x ${\displaystyle x}$에 $대해{\displaystyle }$ P {\displaystyle $y}$을(를${\displaystyle )}$ 만족하는${\displaystyle }$y ${\displaystyle$ y${\displaystyle \}}$이(${\displaystyle 가}$) 존재하면$$$$ P ${\displaystyle P}$을(를$)$ 해결하며$,$ $알고리즘$은 $이러한{\displaystyle }$ y ${\displaystyley y}$을 생성한다$.$

예

잘 알려진 기능 문제는 기능적 부울 만족도 문제, FSAT에 의해 짧게 주어진다.SAT 의사결정 문제와 밀접한 관련이 있는 이 문제는 다음과 같이 정리할 수 있다.

변수 $x{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$… , x ${\displaystyle n_{}}$ ${\$이(가) 포함된$$ 부울 공식 $formula{\displaystyle }$ ${\displaystyle \varphi}$이$($가) 지정 ${\displaystyle x_{}}$ i${\displaystyle {}_{}}$→${\displaystyle }${${\displaystyle \text{TRUE},}$ ${\displaystyle \text{FALSE}}$ $} {\displaystysty x_{{\text}$$TRUE},{\text{$$}\\}{\displaystyle \varphi$}이(가) ${\displaystyle \text{TRUE}}${\$displaystyle${\$text{)$로 평가되는 경우$$$TRUE}}$ 또는$$ 해당 할당이 존재하지 않는지 확인하십시오.

이 경우 $R{\displaystyle }$ ${\displaystyle$ R$}$은(는) 적절히 인코딩된 부울 공식과 만족스러운 할당에 의해 주어진다$$.공식 $\phi {\displaystyle }$ ${\displaystyle \varphi }$과$($와) 함께 제공되는 SAT 알고리즘은 "불만족" 또는 "불만족"만 반환하면 되지만 FSAT 알고리즘은 후자의 경우 일부 만족스러운 할당을 반환하면 된다.

다른 주목할 만한 예로는 판매원이 택한 경로를 묻는 여행 판매원 문제와 요인 목록을 요구하는 정수 인수 문제가 있다.

다른 복잡성 클래스와의 관계

클래스 NP의 임의$$ 결정 문제 $L{\displaystyle }$ ${\displaystyle L}$을(를) 고려하십시오. NP의 정의에 따르면 '예'로 응답되는$$ 각 문제 $인스턴스{\displaystyle }$(instance$)$ x {\$displaystyle$ x$}$에는 $다항식{\displaystyle }$크기 인증서 y {\\\$displaystyle$ y$}$이(가)가 있으며, 이는$$ '예' 답변의 증거 역할을 한다.따라서 이러한 튜플 집합$({\displaystyle x}$ ${\displaystyle ,y}$ ) ${\displaystyle (x,y)}$은(는$$) $관계$를 형성하며$,$ L {\$displaystyle L}$에서 "$지정$된 x ${\displaystyle x}$을($$를) 나타내고$,$ $x{\displaystyle }${\$displaystyty$ x$}$에 대한 $인증서{\displaystyle }$ y ${\\displaysty y}$을 찾는다.이 함수 문제는 $L{\displaystyle }$ ${\displaystyle L}$의 함수 변종이라 불리며$,$ 등급 FNP에 속한다.

FNP 문제의 해결책이 효율적으로 검증될 수 있지만(즉, 입력 길이 측면에서 다항식 시간) 반드시 효율적으로 찾을 수는 없다는 점에서 FNP는 NP의 기능 클래스 아날로그라고 생각할 수 있다.이와는 대조적으로 P의 기능 클래스 아날로그라고 생각할 수 있는 클래스 FP는 다항식 시간에 해결책을 찾을 수 있는 기능 문제로 구성된다.

자기 축소성

위에서 소개한 FSAT 문제는 SAT 문제를 결정하는 서브루틴에 대한 다항식적으로 많은 호출만 사용하여 해결할 수 있음을 관찰하십시오.알고리즘은 먼저 공식 $\phi {\displaystyle }$ ${\displaystyle \varphi }$이(가) 만족스러운지$$ 물어볼 수 있다.그 후에 알고리즘은 변수 $x{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}를 TRUE에$$ 수정하고 다시 물어볼 수 있다.결과 공식이 여전히 만족스러운 경우 알고리즘이 ${\displaystyle {x\mathrm{}}_{}}$ 1 ${\$}를 TRUE에 고정하고$$ ${\displaystyle {x\mathrm{}}_{}}$ $2{\displaystyle {}_{}}$ ${\$}}을 계속 고정하는 경우$,$ 그렇지 않으면 x ${\displaystyle {1\mathrm{}}_{}}$ ${\$}가 FALSE여야 한다고$$ 결정하고 계속한다.따라서 FSAT는 오라클 결정 SAT를 사용하여 다항식 시간에 해결할 수 있다.일반적으로 NP의 문제는 원래의 문제를 결정하는 신탁을 사용하여 다항식 시간에 그 기능 변형을 해결할 수 있다면 자기 축소 가능이라고 한다.모든 NP-완전한 문제는 스스로 줄일 수 있다.정수인자화 문제는 자기축소가 불가능하다는 추측이다^{[by whom?]}.

감소 및 전체 문제 해결

Function problems can be reduced much like decision problems: Given function problems ${\displaystyle \Pi _{R}}$ and ${\displaystyle \Pi _{S}}$ we say that ${\displaystyle \Pi _{R}}$ reduces to ${\displaystyle \Pi _{S}}$ if there exists polynomially-time computable functions ${\displays$$Tyle f}$ 및$$ $g{\displaystyle }$ ${\displaystyle g}($$R{\displaystyle }$ {\$displaystyle R$$}$의 모든 인스턴스 $x{\displaystyle }$ ${\displaystyle$ $x$$}$ 및$$ $S{\displaystyle }$ ${\displaystyle$ S}의$$ 가능한 솔루션 $y{\displaystyle }$ ${\displaystyle y})$에 대해 다음이 유지되도록 한다$.$

• $x{\displaystyle }$ ${\displaystyle x}$에 $R{\displaystyle }$ ${\displaystyle R}$ -solution이$$ 있는$$ 경우 $f{\displaystyle }$ (${\displaystyle x}$) ${\displaystyle f(x)}$에는 $S{\displaystyle }$ ${\displaystyle S}$ -solution이$$ 있다$$.
• $S\implies(x)(x)\in S\implies(x,g(x,y))\re.$

따라서 NP 완전 문제와 유사한 FNP 완전 문제를 정의할 수 있다.

FNP의 모든 문제를 ${\displaystyle {\pi }_{}}$ R ${\$ $_$${$R$}$로 줄일 수 있다면 문제 ${\displaystyle r_{}}$ R ${\${R}}은(는) FNP-C 또는 FNPC로 구분된다$.$따라서 FSAT 문제도 FNP-완전한 문제로, ${\displaystyle \mathbf{FP}}$= ${\displaystyle \mathbf{FNP}}${\$displaystyle \mathbf {P} =\mathbf$ {P$}$ =\$displaysty \mathbf {FP} =\mathbf {F}$인 경우에만$$ 해당 $P{\displaystyle \mathbf{}}$= ${\displaystyle \mathbf{NP}}$$}$을(으)로 유지한다$.$

총 함수 문제

함수 문제를 정의하는 데 사용되는$$ $R{\displaystyle (x}$, y${\displaystyle }$) ${\displaystyle R(x,y)}$은(는) 불완전하다는 단점이 있다.${\displaystyle \mathrm{모든}}$ 입력 $x{\displaystyle }$ ${\displaystyle x}$이(${\displaystyle 가}$) (${\displaystyle }$x${\displaystyle }$, ${\displaystyle y}$) ${\displaystyle \in }$ R ${\displaystyle (x,y)\in R}$과 같은 상대적인 $y{\displaystyle }$ ${\displaystyle y}$을(를) 가지고$$ 있는 것은 아니다$.$ 따라서 증명의 계산성에 대한 문제는 그 존재의 문제와 분리되지 않는다.이 문제를 극복하기 위해서는 FNP의 하위 등급으로 등급 TFNP를 산출하는 전체 관계에 대한 기능 문제의 제약을 고려하는 것이 편리하다.이 세분류는 해결책이 보장되는 특정 전략 게임에서 순수 나시 평형도의 연산 등의 문제를 담고 있다.또한 TFNP에 FNP-완전한 문제가 있는 경우, N ${\displaystyle \mathbf{P}}$= ${\displaystyle \mathbf{\text{co-NP}}}$ ${\$ 뒤에 따른다$.$

참고 항목

• 의사결정 문제
• 검색문제
• 카운팅 문제(복잡성)
• 최적화 문제

참조

이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 보다 정확한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2015년 10월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)