FNP(복잡성)

계산 복잡성 이론에서 복잡성 등급 FNP는 의사결정 문제 등급 NP의 기능 문제 확장이다.기술적으로는 다음과 같은 형식적 정의가 설명하듯이 기능이 아닌 이항 관계의 한 부류이기 때문에 명칭은 다소 잘못된 것이다.

2진수 관계 P(x,y)는 y가 x보다 최대 다항식적으로 길며, P(x,y)가 x와 y를 모두 보유하는지 여부를 결정할 수 있는 결정론적 다항식 시간 알고리즘이 있는 경우에만 FNP에 있다.^[1]

이 정의는 비계수주의를 포함하지 않으며 NP의 검증자 정의와 유사하다.

모든 FNP 관계에 직접적으로 대응하는 NP 언어가 있으며, 때로는 FNP 관계에 의해 유도되거나 이에 대응되는 의사결정 문제라고도 한다.P(x,y)가 어느 정도 y를 갖는 모든 x를 취함으로써 형성된 언어지만, 특정 의사결정 문제에 대해 둘 이상의 FNP 관계가 있을 수 있다.

많은 NP-완전한 문제를 포함한 NP의 많은 문제들은 만족스러운 과제, 그래프 컬러링 또는 특정 크기의 집단과 같은 특정 물체가 존재하는지 여부를 질문한다.이러한 문제의 FNP 버전은 그것이 존재하는지 여부뿐만 아니라 만약 존재한다면 그것의 가치가 무엇인지 묻는다.이것은 모든 NP-완전 문제의 FNP 버전이 NP-hard라는 것을 의미한다.Bellare와 Goldwasser는 1994년에 FNP 버전이 자체 축소 가능하지 않을 정도로 NP에 문제가 있다는 몇몇 표준 가정을 사용하여 보여주었는데, 이는 그들이 상응하는 의사결정 문제보다 더 어렵다는 것을 암시한다.^[2]

FNP의 각 P(x,y)에 대해, P(x,y)와 관련된 검색 문제는 다음과 같다: x가 주어진 경우, P(x,y)가 보유하는 y를 찾거나 그러한 y가 존재하지 않는다고 명시한다.FNP의 모든 관계에 대한 검색 문제는 P = NP인 경우에만 다항 시간 내에 해결할 수 있다.이 결과는 보통 "P = NP인 경우에만 FP = FNP"로 명시되지만, 이 진술이 사실이라면 FP와 FNP를 재정립하여 FP와 FNP의 구성원이 관계가 아니라 관계와 관련된 검색 문제가 되도록 하는 것이 필요하다.

할인

관련 검증 알고리즘 A₁, A와₂ 함께 P와₁ P를₂ FNP의 두 가지 문제로 한다. 감소 P와₁ P는₂ 다음과^[3] 같이 효율적으로 계산 가능한 두 가지 기능인 f와 g로 정의된다.

• f 맵 입력 x - P₁ - 입력 f(x₂) - P ;
• g maps 출력 y ~ P₂, 출력 g(y) ~ P₁;
• 모든 x 및 y에 대해₂: A(f(x)),y가 true를 반환하는 경우, A(x₁, g(y)가 true를 반환한다.
• 모든 x에 대해: A₂(f(x)),y가₁ 거짓을 반환하면 A(x, g(y)는 모든 y에 대해 거짓을 반환한다.

관련 복잡도 클래스

• FP는 주어진 x에 P(x,y)가 보유하는 y를 찾는 다항 시간 알고리즘이 있는 이진 관계 집합이다.FNP와 FP의 관계는 NP와 P의 관계와 유사하다.
• TFNP는 FNP의 하위 집합이다. TFNP는 모든 x에 대해 P(x,y)가 보유하는 y가 적어도 하나 있는 FNP의 관계를 포함한다.

참조

외부 링크

• 복잡성 동물원: FNP