다항 시간 감소

계산 복잡성 이론에서 다항식 시간 단축은 한 문제를 다른 문제를 사용하여 해결하는 방법이다. 하나는 두 번째 문제를 해결하는 가상 서브루틴이 존재한다면, 두 번째 문제에 대한 입력으로 변환하거나 축소하고 서브루틴을 한 번 이상 호출함으로써 첫 번째 문제를 해결할 수 있다는 것을 보여준다. 첫 번째 문제를 두 번째 문제로 변환하는 데 필요한 시간과 서브루틴을 호출하는 횟수가 모두 다항식이라면 첫 번째 문제는 두 번째 문제로 다항식 시간을 줄일 수 있다.^[1]

다항 시간 단축은 첫 번째 문제가 두 번째 문제에 대한 효율적인 알고리즘이 존재할 때마다 첫 번째 문제도 첫 번째 문제에 대해 존재하기 때문에 두 번째 문제보다 어렵지 않다는 것을 증명한다. 대조적으로, 첫 번째 문제에 대한 효율적인 알고리즘이 존재하지 않는다면, 두 번째 문제 역시 존재하지 않는다.^[1] 다항 시간 감소는 복잡성 등급과 해당 등급의 완전한 문제를 모두 정의하기 위한 복잡성 이론에서 자주 사용된다.

감산 유형

다항식 시간 감소의 가장 일반적인 세 가지 유형은 다항식 시간 다대일 감소, 진리표 감소, 튜링 감소 등이다. 이들 중 가장 많이 사용되는 것은 다항일감축이며, 경우에 따라서는 다항일수 다항일감축이라는 문구를 사용하여 '다항일감축'을 의미하기도 한다.^[2] 가장 일반적인 감소는 튜링 감소이고 가장 제한적인 감소는 그 사이의 공간을 점유하는 진실 테이블 감소와 함께 다수의 감소다.^[3]

다대일감소

다항 시간 다항 시간 다항 시간 다항 시간 A에서 문제 B로 감소(둘 다 보통 의사결정 문제로 요구됨)는 다항 시간 알고리즘으로, 변환된 문제가 원래 문제와 동일한 출력을 가지도록 문제 A로 입력을 변환한다. 문제 A의 인스턴스 x는 문제 B의 인스턴스 y를 생성하기 위해 이 변환을 적용하고, 문제 B의 알고리즘에 대한 입력으로 y를 제공하고, 그 출력을 반환함으로써 해결할 수 있다. 다항식 시간 다항식 감소는 다항식 변환 또는 Richard Karp의 이름을 딴 Karp 감소라고도 알려져 있다. 이러한 유형의 감소는 $A{\displaystyle }$ ${\displaystyle {}_m^{}}$ ${\displaystyle {}_{}^{}}$ B ${\displaystyle A\leq _{m}^{p}B}$ 또는$$ $A{\displaystyle }$ ${\displaystyle {}_{}}$ p ${\displaystyle {}_{}}$ ${\displaystyle A\leq _{p}B}$로 표시된다$.$^[4][1]

진실테이블감소

문제 A에서 문제 B로 다항 시간 진리표 감소(두 가지 의사결정 문제)는 원래 문제의 출력이 B에 대한 출력의 함수로 표현될 수 있도록 문제 A로 입력을 문제 B로 고정된 입력 수로 변환하기 위한 다항 시간 알고리즘이다. B에 대한 출력을 A에 대한 출력에 매핑하는 기능은 모든 입력에 대해 동일해야 하며, 이를 진리 표로 표현할 수 있다. 이러한 유형의 감소는 $A{\displaystyle }$ ${\displaystyle {}_{}^{}}$ ${\displaystyle t_{}^{}}$ ${\displaystyle P_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle A\leq _{tt}^{P}B}$라는 표현으로 나타낼 수 있다$.$^[5]

튜링 감소

문제 A에서 문제 B로 다항식 시간 튜링 감소는 문제 B에 대한 서브루틴에 대한 다항식 통화 수와 해당 서브루틴 통화 외부의 다항식 시간을 사용하여 문제 A를 해결하는 알고리즘이다. 다항식 시간 튜링 감소는 스티븐 쿡의 이름을 딴 쿡 감소라고도 알려져 있다. .[4]Many-one 감소가 전화 문제 B를 위해 서브 루틴은 위해서 만들어진 번호는 정확히 1과 retur로서의 힘을 감소에 의해 반환됩니다 같은 값 튜링 감축이라는 제한된 변종으로 간주될 수 있습니다 이 형식의 감소는 표현에 의한≤ TPB{\displaystyle A\leq_{T}^{P}B}표시될 수 있다.ned 서브루틴으로

완성도

주어진 복잡도 등급 C와 감소 ≤에 대한 완전한 문제는 C에 속하는 문제 P이다. 예를 들어, C의 모든 문제 A는 감소 A p P를 가지고 있다. 예를 들어, 문제는 NP에 속하고 NP의 모든 문제는 다항식 시간 다수의 감소를 가지고 있다. NP에 속하는 문제는 알려진 NP-완전 문제로부터 NP-완전성 문제를 단일 다항식 시간 다수 1 단축을 찾아냄으로써 NP-완전성을 증명할 수 있다.^[6] 다항 시간 다항 시간 다항 시간 단축은 PSPACE 완성 언어와 EXPTIME 완성 언어를 포함한 다른 복잡성 클래스의 전체 문제를 정의하기 위해 사용되었다.^[7]

P의 모든 의사결정 문제(다항 시간 의사결정 문제의 종류)는 다항 시간 다대일 축소에 의해 다른 모든 비경쟁적 의사결정 문제(비경쟁적 입력이 모든 입력의 출력이 동일하지 않다는 것을 의미)로 축소될 수 있다. 문제 A의 인스턴스를 B로 변환하려면 다항 시간 내에 A를 푼 다음 솔루션을 사용하여 다른 답으로 문제 B의 두 인스턴스 중 하나를 선택하십시오. 따라서 L, NL, NC, P 자체와 같은 P 내의 복잡성 클래스의 경우, 다항 시간 단축을 사용하여 완전한 언어를 정의할 수 없다: 만약 이러한 방식으로 사용된다면 P의 모든 비경쟁적 문제가 완료된다. 대신에, 로그 공간 감소 또는 NC 감소와 같은 약한 감소는 P-완전 문제와 같은 이러한 세분류에 대한 완전한 문제의 클래스를 정의하는 데 사용된다.^[8]

복잡성 클래스 정의

복잡도 등급 NP, PSPACE 및 EXPTIME의 정의는 감소를 포함하지 않는다. 즉, 감소는 이러한 등급에 대한 완전한 언어의 정의에서만 연구에 포함된다. 그러나 경우에 따라 복잡도 등급은 감소에 의해 정의될 수 있다. $만약$ C가 의사결정 문제라면, $A$의 $언어$인$A로 구성$된 복잡도 클래스 C를 ${\displaystyle {}_{}^{}}$할 수 있다$.$$$이 경우 C는 자동으로 C에 대해 완성되지만, C도 다른 완전한 문제를 가질 수 있다$.$

그 예로는 NP-hard로 알려져 있고 PSPACE로 알려져 있지만 다항식 계층 구조에서 NP-hard로 알려져 있는 계산 문제인 reals의 실존 이론으로부터 정의된$$ 복잡도 ${\displaystyle 클래스\mathbb{}}$ $\exists {\displaystyle \mathrm{}}$ R ${\$}이(가)가 있다. ${\displaystyle \mathrm{\exists }}$ ${\displaystyle R\mathbb{}}$ ${\$은 다항식 시간 다수를 실제 실존 이론으로 축소하는 문제의 집합이며, 비방향 그래프의 직선 교차 번호 결정과 같은 몇 가지 다른 완전한 문제가 있다. $\exists {\displaystyle \mathrm{}}$ ${\displaystyle R\mathbb{}}$ ${\$의 각 문제는 PSPACE에 속하는 속성을 상속하며$$, 각 $\exists {\displaystyle \mathrm{}}$ ${\displaystyle R\mathbb{}}$ ${\$-완전한$$ 문제는 NP-hard이다.^[9]

마찬가지로, 복잡도 등급 GI는 그래프 이형성 문제로 축소될 수 있는 문제로 구성된다. 그래프 이형성은 NP와 co-AM에 모두 속하는 것으로 알려져 있으므로, 이 세분류의 모든 문제에 대해서도 마찬가지다. 문제는 이 세분류에 대해 완전하다면 GI-완전하다. 그래프 이형성 문제 자체는 GI-완전하다. 다른 몇몇 관련 문제들과 마찬가지로.^[10]

참고 항목

• Karp의 21개의 NP 완성 문제

외부 링크

• MIT OpenCourseWare: 16. 복잡성: P, NP, NP-완전성, 감소

참조