FP(복잡성)

계산 복잡성 이론에서 복잡성 등급 FP는 다항 시간 내에 결정론적 튜링 기계로 해결할 수 있는 기능 문제의 집합이다.의사결정 문제 클래스 P의 기능 문제 버전이다.대략적으로 말하면, 무작위화 없이 클래식 컴퓨터로 효율적으로 계산될 수 있는 기능의 등급이다.

FP와 P의 차이점은 P의 문제는 1비트, 예/아니오 답이 있는 반면 FP의 문제는 다항식 시간에 계산될 수 있는 출력을 가질 수 있다는 것이다.예를 들어, 두 숫자를 추가하는 것은 FP 문제인 반면, 그 합계가 홀수인지를 결정하는 것은 P에 있다.^[1]

다항식 시간 함수 문제는 다항식 시간 감소를 정의하는데 기본적이며, NP-완전한 문제의 등급을 정의하는 데 사용된다.^[2]

형식 정의

FP는 공식적으로 다음과 같이 정의된다.

$x{\displaystyle }$ ${\displaystyle x}$이$($가) $P{\displaystyle (x}$${\displaystyle }$, ${\displaystyle y}$ ) ${\displaystyle$$p$$(x,y$)}이(가) 보유하는$$ $일부$$$y {\$displaystyle$ $y$$}$을(를) 찾을 수 있는 결정론적 다항식 $시간$ 알고리즘이 있는 경우에만 2진수 $관계{\displaystyle }$ P${\displaystyle (}$$x$ ${\displaystyle ,}$${\displaystyle y}$)가 FP에 있다.

관련 복잡도 클래스

• FNP는 주어진 x와 y에 P(x,y)의 보유 여부를 확인하는 다항 시간 알고리즘이 있는 이진 관계 집합이다.P와 FP가 밀접하게 연관되어 있듯이, NP는 FNP와 밀접한 관계가 있다. P = NP인 경우에만 FNP = FNP이다.
• 로그 공간을 사용하는 기계는 다항식적으로 구성이 많으므로 로그 공간에서 계산할 수 있는 기능 문제 집합인 FL이 FP에 포함되어 있다.FL = FP인지는 알려지지 않았다. 이는 의사결정 등급 P와 L이 동일한지 여부를 결정하는 문제와 유사하다.

참조

외부 링크

• 복잡성 동물원: FP