파라미터화된복잡도

컴퓨터 과학에서, 매개 변수화된 복잡도는 입력 또는 출력의 여러 매개 변수와 관련하여 컴퓨터 문제를 고유 난이도에 따라 분류하는 데 초점을 맞춘 계산 복잡도 이론의 한 분야이다.그런 다음 문제의 복잡성은 이러한 매개변수의 함수로 측정됩니다.이것에 의해, 문제의 복잡성이 입력의 비트수의 함수로만 측정되는 종래의 설정보다, NP-하드 문제를 보다 세밀하게 분류할 수 있습니다.매개 변수화된 복잡성에 대한 첫 번째 체계적인 작업은 다우니 & 펠로우즈(1999)에 의해 수행되었다.

P np NP라는 가정 하에 입력 크기만으로 복잡도를 측정할 때는 초다항 실행 시간이 필요하지만 입력 크기에서는 다항식이고 $파라미터$ k에서는 지수적인 시간에는 계산 가능한 많은 자연 문제가 존재한다.따라서 k가 작은 값으로 고정되고 k에 $대한$ 함수의 성장이 상대적으로 $작더라도$ 이러한 문제는 전통적인 분류가 "난해"임에도 불구하고 여전히 "난해"로 간주될 수 있다.

NP-완전 또는 NP-하드 문제에 대한 효율적이고 정확한 결정론적 해결 알고리즘의 존재는 입력 파라미터가 고정되어 있지 않은 경우 가능성이 낮은 것으로 간주됩니다.이러한 문제에 대해 알려진 모든 해결 알고리즘은 입력의 총 크기에서 지수(또는 적어도 다항식)인 시간이 필요합니다.그러나 일부 문제는 고정된 파라미터의 크기에서만 기하급수적인 알고리즘과 입력 크기의 다항식 알고리즘으로 해결할 수 있습니다.이러한 알고리즘은 고정 파라미터의 작은 값에 대해 문제를 효율적으로 해결할 수 있기 때문에 고정 파라미터 추적(fpt-) 알고리즘이라고 불립니다.

일부 $매개$ 변수 k가 고정된 문제를 매개 변수화된 문제라고 합니다.이러한 fpt-algorithm을 가능하게 하는 파라미터화 문제는 FPT 클래스에 속하는 고정 파라미터 처리 가능한 문제라고 하며, 파라미터화 복잡성 이론의 초기 명칭은 고정 파라미터 처리 가능성이었다.

$많은$ 문제들은 다음과 같은 형태를 가지고 있다: 객체 x와 $음$ 이 아닌 정수 k가 주어졌을 때, x는 k에 $의존$ 하는 속성을 $가지고$ 있는가?예를 들어, 정점 덮개 문제의 경우 매개 변수는 덮개의 정점 수가 될 수 있습니다.예를 들어, 많은 애플리케이션에서 오류 수정을 모델링할 때, 총 입력 크기에 비해 매개변수가 "작다"고 가정할 수 있습니다.그러면 입력 크기가 아닌 k $단위$ 로만 지수화된 알고리즘을 찾는 것이 어렵습니다.

이와 같이 파라미터화된 복잡도는 2차원 복잡도 이론으로 볼 수 있다.이 개념은 다음과 같이 공식화됩니다.

파라미터화된 문제는

L\subseteq \Sigma ^{*}\times \mathbb {N}

L

L\subseteq \Sigma ^{*}\times \mathbb {N}

×

L\subseteq \Sigma ^{*}\times \mathbb {N}

×

L\subseteq \Sigma ^{*}\times \mathbb {N}

{\

displaystyle

L

\subseteq \Sigma ^{*}\times \mathbb {N

입니다.

\Sigma

서

{\

\

displaystyle \Sigma

}는

\Sigma

유한 알파벳입니다.두 번째 컴포넌트는 문제의 파라미터라고 불립니다.

파라미터화된

문제

L은 " ( x ,

(x,k)\in L

)

(x,k)\in L

L

(x,k)\in L

\

displaystyle ( x

,

k

)\

in

L

(x,k)\in L

이라는 질문이 실행

f(k)\cdot |x|^{O(1)}

f (

f(k)\cdot |x|^{O(1)}

)

f(k)\cdot |x|^{O(1)}

f(k)\cdot |x|^{O(1)}

O (

f(k)\cdot |x|^{O(1)}

)\

display

f (

k

)\

cdot

x^ {

O

(

1

f(k)\cdot |x|^{O(1)}

로 결정될 경우 고정 파라미터 처리 가능합니다.

여기

서 f는

k

에만 의존하는 임의의 함수입니다.대응하는 복잡도 클래스는 FPT라고 불립니다.

예를 들어 $O(kn+1.274^{k})$ O( $O(kn+1.274^{k})$ n + $O(kn+1.274^{k})$ . $O(kn+1.274^{k})$ $)$ $시간$ (\^[1] $style$ O $(kn+1.274^{k})$ 으로 $O(kn+1.274^{k})$ 정점 커버 문제를 해결하는 알고리즘이 있습니다. $여기$ 서 n은 정점 $수이고$ k는 정점 커버의 크기입니다.즉, 정점 커버는 솔루션의 크기를 모수로 하여 고정 모수를 추적할 수 있습니다.

복잡도 클래스

FPT

FPT에는 고정 파라미터의 다루기 쉬운 문제가 포함되어 있습니다.이러한 문제는 f $f(k)\cdot {|x|}^{O(1)}$ $k$ ) $f(k)\cdot {|x|}^{O(1)}$ O ( $f(k)\cdot {|x|}^{O(1)}$ ) $f(k)\cdot {|x|}^{O(1)}$ \ $displaystyle$ f ( $k$ ) \ $cdot$ { $x$ }^{ $O$ ( $1$ )}} $f(k)\cdot {|x|}^{O(1)}$ 내에 해결할 수 있는 문제입니다.일반적으로 이 함수는 $2^{O(k)}$ O ( $2^{O(k)}$ ) \ $displaystyle$ 2 $^{O(k)}$ 처럼 $2^{O(k)}$ 단일 지수함수로 간주되지만, 이 정의에서는 더욱 빠르게 성장하는 함수를 허용합니다.이것은 이 수업의 초기 역사의 많은 부분을 위해 필수적이다.정의의 중요한 부분은 f $f(n,k)$ ( $f(n,k)$ , $f(n,k)$ ) { $displaystyle$ f ( $n$ , $f(n,k)$ k ) $f(n,k)$ 의 함수( n , k )를 제외하는 것입니다( $n^{k}$ k \ $n^{k}$ n^ { $k$ } $n^{k}$ 。FPL(고정 파라미터 선형) 클래스는 계산 가능한 $함수$ ^[2]f에 대해 $f(k)\cdot |x|$ f ( $f(k)\cdot |x|$ x x $f(k)\cdot |x|$ \ $display style$ f $(k)\cdot$ x $}$ 로 $f(k)\cdot |x|$ 해결할 수 있는 문제의 클래스입니다.따라서 FPL은 FPT의 서브클래스가 됩니다.

변수 수에 따라 모수화된 만족도 문제가 한 예입니다.k개의 변수를 $가진$ $크기$ m의 특정 공식은 $O(2^{k}m)$ O( $O(2^{k}m)$ m $O(2^{k}m)$ 에서 브루트 포스로 확인할 수 있습니다. $순서$ $n$ 의 그래프에서 $크기$ k의 $정점 커버$ 는 $O(2^{k}n)$ O $($ n $O(2^{k}n)$ 에서 찾을 수 있습니다.따라서 이 문제는 FPT에서도 발생합니다.

FPT에 없는 것으로 생각되는 문제의 예로는 색상 수에 따라 파라미터화된 그래프 색칠이 있습니다.3-displaystyle은 NP-hard이며, k $k=3$ $(\displaystyle$ k= $3)$ 에 대한 $k=3$ f $(k) n O(1)$ 의 $f(k)n^{O(1)}$ 그래프 $k=3$ k-display에 대한 $알고리즘$ 은 입력 크기에서 다항식 시간에 실행된다.따라서 색수에 의해 매개 변수화된 그래프 색칠이 FPT이면 P = NP이다.

FPT에는 여러 가지 대체 정의가 있습니다.예를 들어 실행시간 요건은 f $f(k)+|x|^{O(1)}$ ( $f(k)+|x|^{O(1)}$ ) + $f(k)+|x|^{O(1)}$ O ( $f(k)+|x|^{O(1)}$ ) { $displaystyle$ f $(k)$ + x $^{O(1)}$ 로 $f(k)+|x|^{O(1)}$ 할 수 있습니다.또한 파라미터화된 문제는 이른바 커널이 있는 경우 FPT에 있습니다.커널라이제이션은 원래 인스턴스를 "하드 커널"로 줄이는 전처리 기술입니다. 하드 커널은 원래 인스턴스와 동일하지만 파라미터의 함수에 의해 제한되는 크기를 가진 훨씬 작은 인스턴스일 수 있습니다.

FPT는 fpt-reduations라고 하는 파라미터화된 감소 개념 하에서 닫힙니다.이러한 축소에 의해 문제의 인스턴스 $)$ 가 $(x,k)$ 다른 문제의 동등한 인스턴스 $(x',k')$ $k'\leq g(k)$ $(x,k)$ $(x',k')$ $k'\leq g(k)$ 로 $(x',k')$ 변환되어 $f(k)\cdot p(|x|)$ leq g $(k$ $($ $x, k$ $)\$ $displaystyle$ $($ $x$ ,k $))로 계산됩니다.$ $e$ p $\displaystyle$ p는 $p$ 다항식입니다.

FPT에는 모든 다항식 시간 계산 가능한 문제가 포함되어 있습니다.더욱이, 효율적인 다항식 시간 근사 체계(EPTAS)를 가능하게 하는 NP의 모든 최적화 문제를 포함한다.

W 계층

W 계층은 계산 복잡도 클래스의 집합입니다.각 인스턴스 $(x,k)$ x , k ) { $(x,k)$ ( $x$ , $(x,k)$ k )\ $displaystyle (x$ , k $(x,k)$ )\ $in$ L $(x,k)\in L$ l ( $(x,k)\in L$ x , $(x,k)$ )과 같이 최대 i를 가진 조합회선으로 변환될 수 있는 경우 ( $(x,k)\in L$ , $(x,k)\in L$ ) $(x,k)\in L$ l L $(x,k)\in L$ \ $display$ ( $x$ , $k$ )\ in L 이 $(x,k)\in L$ 할당에 정확히 일치하는 경우에만 파라미터화된 문제가 클래스 W [i]에 있습니다.위트는 입력에서 출력까지의 경로에 무제한 팬인이 있는 논리 유닛의 최대 수입니다.패스의 논리 유닛의 합계수(깊이라고 불립니다)는 문제의 모든 인스턴스에 대해 유지되는 상수에 의해 제한되어야 합니다.

$F$ $i\leq j$ ${\mathsf {FPT}}=W[0]$ [ $]{$ $displaystyle$ { $FPT$ $} = W$ [ $W[i]\subseteq W[j]$ ${\mathsf {FPT}}=W[0]$ ] $W[i]\subseteq W[j]$ [ i $W[i]\subseteq W[j]$ ] ] $W[i]\subseteq W[j]$ [ $W[i]\subseteq W[j]$ ]{ $displaystyle$ W [ $i$ $W[i]\subseteq W[j]$ ]\ $subseteq$ $W[i]\subseteq W[j]$ W [ $j$ $i\leq j$ ] ${\mathsf {FPT}}=W[0]$ $W[i]\subseteq W[j]$ f f $。$ W 계층의 클래스도 fpt-reduction에 의해 닫힙니다.

많은 자연적 계산 문제가 낮은 수준인 W[1]와 W[2]를 차지합니다.

W[1]

W[1]-완전 문제의 예는 다음과 같습니다.

지정된 그래프에 k 크기의 클리크가 포함되어 있는지 확인
특정 그래프에 크기 k의 독립 집합이 포함되어 있는지 확인
주어진 비결정론적 단일 테이프 튜링 기계가 k단계 내에서 받아들일지 여부를 결정한다("짧은 튜링 기계 수용" 문제).이것은 f(k) 테이프가 있는 비결정론적 튜링 기계에도 적용되며 심지어 f(k) 차원 테이프가 있는 f(k) 테이프의 f(k)까지 포함되지만, 이 확장에도 불구하고 f(k) 테이프 알파벳 크기에 대한 제한은 고정 파라미터로 다루기 쉽다.결정적으로, 각 단계에서 튜링 기계의 분기는 입력의 크기인 n에 의존하도록 허용된다.이런 방식으로, 튜링 기계는 n개의 계산 경로를 탐색할^O(k) 수 있다.

W[2]

W[2]-완전 문제의 예는 다음과 같습니다.

특정 그래프에 크기 k의 지배적인 세트가 포함되어 있는지 확인
주어진 비결정적 멀티테이프 튜링 기계가 k단계 내에서 받아들일지 여부를 결정한다("짧은 멀티테이프 튜링 기계 수용" 문제).결정적으로 분기는 테이프 수와 마찬가지로 n(W[1] 배리언트 등)에 의존할 수 있습니다.대체 W[2]-완전 공식은 단일 테이프 튜링 기계만 허용하지만 알파벳 크기는 n에 따라 달라질 수 있습니다.

W[t]

$W[t]$ [ $]$ \ $displaystyle$ W[ $t$ ] { $displaystyle$ d $d\geq t$ \ $geq$ $d\geq t$ : $W[t,d]$ W [ $W[t,d]$ , $d\geq t$ $W[t,d]$ ]{ $displaystyle W$ [ $W[t,d]$ , $d ]$ 는 $W[t,d]$ 이 문제에 대응하는 파라미터화된 문제의 클래스입니다 $W[t]=\bigcup _{d\geq t}W[t,d]$ $W[t]=\bigcup _{d\geq t}W[t,d]$ $W[t]=\bigcup _{d\geq t}W[t,d]$ $[t,d$

여기서 Weighted Weft-t-Depth-d SAT는 다음 문제입니다.

입력: 최대 $d$ 및 $최대$ weft 깊이와 $숫자$ k의 부울 공식입니다.깊이는 뿌리에서 잎까지의 경로 상의 최대 게이트 수이며, 위트는 뿌리에서 잎까지의 경로 상의 최소 3개의 팬 인 게이트 수이다.
질문:.공식에 해밍 무게의 배분이 정확히 $k인가$ 요?

It can be shown that for $t\geq 2$ the problem Weighted $t$ -Normalize SAT is complete for $W[t]$ under fpt-reductions.^[3]여기서 Weighted t-Normalize SAT는 다음 문제입니다.

입력: 최대 $t$ 깊이의 부울 공식으로, 맨 위에 AND-게이트가 있고 $숫자$ k가 있습니다.
질문:.공식에 해밍 무게의 배분이 정확히 $k인가$ 요?

W[P]

W[P]는 $h(k)\cdot {|x|}^{O(1)}$ h ( $h(k)\cdot {|x|}^{O(1)}$ x $h(k)\cdot {|x|}^{O(1)}$ ( $h(k)\cdot {|x|}^{O(1)}$ $){$ $displaystyle$ h ( $k$ )\ $cdot$ { $x$ }^{ $O$ (1)}: 시간 $h(k)\cdot {|x|}^{O(1)}$ 튜링 $O(f(k)\cdot \log n)$ 으로 $O(f(k)\cdot \log n)$ O ( $O(f(k)\cdot \log n)$ ) $O(f(k)\cdot \log n)$ $log$ n $O(f(k)\cdot \log n)$ \ $displaystyle$ O ( $k$ )\ $cdot$ } 비결정론적 $O(f(k)\cdot \log n)$ 선택지에 의해 결정될 수 있는 문제의 $클래스$ 입니다.k-제한 튜링 머신).Flum & Grohe (2006)

FPT는 W[P]에 포함되어 있으며, 포함이 엄격한 것으로 생각된다.단, 이 문제를 해결하면 P 대 NP 문제에 대한 해결책이 됩니다.

미파라미터 계산의 복잡성에 대한 기타 접속은 회선의 만족도를 $\exp(o(n))m^{O(1)}$ exp $\exp(o(n))m^{O(1)}$ ( $\exp(o(n))m^{O(1)}$ ( $\exp(o(n))m^{O(1)}$ ) $\exp(o(n))m^{O(1)}$ ( 1 $\exp(o(n))m^{O(1)}$ )\ $displaystyle \exp ( o$ ( n )m $^{O$ (1 $\exp(o(n))m^{O(1)}$ 내에 결정할 수 있는 경우 또는 이러한 모든 언바인드 언어를 인식할 수 있는 경우에 한해 FPT가 W[P]와 동일하다는 것입니다.f $f(n)\log n$ ( $f(n)\log n$ $f(n)\log n$ log $f(n)\log n$ n \ $displaystyle$ f $(n)\log$ n $}$ 비결정론적 선택은 $f(n)\log n$ P에 있다.

W[P]는 대략적으로 n개 $항목$ 의 $집합$ S가 있으며, 특정 속성이 유지되도록 $크기$ k의 $T\subset S$ T $T\subset S$ S \ $displaystyle$ T \ $subset$ S 를 $T\subset S$ 찾고자 하는 문제의 클래스라고 생각할 수 있습니다.2진수로 저장된 k개의 $정수$ 목록으로 선택을 인코딩할 수 있습니다.이들 중 가장 높은 숫자는 $n$ 이므로 각 번호에 $\lceil \log _{2}n\rceil$ " $\lceil \log _{2}n\rceil$ 2 $\lceil \log _{2}n\rceil$ $"\displaystyle \lceil$ \ $log$ _ ${2}n\rceil}$ 비트가 $\lceil \log _{2}n\rceil$ 필요합니다. $k\cdot \lceil \log _{2}n\rceil$ 선택지를 부호화하려면 k $k\cdot \lceil \log _{2}n\rceil$ " " $k\cdot \lceil \log _{2}n\rceil$ " $k\cdot \lceil \log _{2}n\rceil$ $k\cdot \lceil \log _{2}n\rceil$ " $k\cdot \lceil \log _{2}n\rceil$ n " $k\cdot \lceil \log _{2}n\rceil$ " { $displaystyle$ k \ $cdot$ \ $lceil$ \ $log$ _ ${2}n$ \ $rceil }$ 의 $k\cdot \lceil \log _{2}n\rceil$ 총 비트가 필요합니다.따라서 O $O(k\cdot \log n)$ ( $O(k\cdot \log n)$ log $O(k\cdot \log n)$ n $O(k\cdot \log n)$ ) { $displaystyle$ O $( k$ \ $cdot$ \ $log$ n $O(k\cdot \log n)$ ) }비확정적인 $O(k\cdot \log n)$ 선택을 $O(k\cdot \log n)$ $T\subset S$ S $T\subset S$ \ $subset$ S 를 선택할 $T\subset S$ 수 있습니다.

XP

XP는 일부 계산 가능한 $함수$ f에 대해 시간 $n^{f(k)}$ ( $){$ n $^{f(k)}}$ 로 $n^{f(k)}$ 해결할 수 있는 파라미터화된 문제의 클래스입니다.이러한 문제는 고정 k의 각 "슬라이스"가 k마다 다른 지수를 가지지만 다항식 알고리즘을 갖는다는 점에서 슬라이스 다항식이라고 불린다.이것을 단지 k의 각 값에 대해 다른 상수 프리팩터를 허용하는 FPT와 비교해 보자. XP에는 FPT가 포함되어 있으며, 이 격납은 대각화에 의해 엄격한 것으로 알려져 있다.

파라 NP

para-NP는 시간 f ( k $f(k)\cdot |x|^{O(1)}$ ) $f(k)\cdot |x|^{O(1)}$ x O ( $f(k)\cdot |x|^{O(1)}$ ){ $displaystyle$ f $(k)\cdot$ x ^{ $O(1)}$ 의 $f(k)\cdot |x|^{O(1)}$ 비결정론적 알고리즘으로 해결할 수 있는 $파라미터화$ 된 문제의 클래스입니다. ${\textsf {FPT}}={\textsf {para-NP}}$ ${\textsf {FPT}}={\textsf {para-NP}}$ ${\textsf {FPT}}={\textsf {para-NP}}$ ${$ { $FPT}$ $=$ $para-NP}$ 인 경우는 ${\textsf {FPT}}={\textsf {para-NP}}$ ${\textsf {P}}={\textsf {NP}}$ P ${\textsf {P}}={\textsf {NP}}$ $para-textsf {para-NP$ ^[4]인 것으로 알려져 있습니다.

NP $(\$ 의 ${\textsf {NP}}$ 경우 문제는 파라-NP-hard입니다.파라미터의 상수값이 이미 hard입니다. $즉$ , 고정k의 "슬라이스"는 ${\textsf {NP}}$ NP(\ $displaystyle\textsf {NP})-$ hard입니다 ${\textsf {NP}}$ . ${\textsf {para-NP}}$ 된 문제 $($ $para-NP)$ 는 P $= NP$ (\ $\displaystyle\$ p ${\textsf {P}}={\textsf {NP}}$ 가 아니면 ${\textsf {P}}={\textsf {NP}}$ XP $(\$ $displaystyle\$ $displaystyle$ $\xp})$ 에 ${\textsf {para-NP}}$ 속할 수 없습니다. $para-NPara$ 의 ${\textsf {para-NP}}$ 클래식한 예입니다 $.$ k $색상$ 으로 매개 변수화된 그래프 색칠입니다. ${\textsf {NP}}$ 색상은 이미 ${\textsf {NP}}$ NP(\ $displaystyle\$ displaystyle ${\textsf {NP}}$ { $NP})$ - k $k=3$ (\ $displaystyle$ k $=3$ )에 $k=3$ 딱딱합니다(그래프 색칠#계산 복잡도 참조).

계층

A 계층은 W 계층과 유사한 계산 복잡도 클래스의 모음입니다.그러나 W 계층이 NP에 포함된 계층인 반면, A 계층은 고전적인 복잡성에서 다항식 시간 계층을 더 가깝게 모방합니다.A[1] = W[1]가 유지되는 것으로 알려져 있습니다.

메모들

^ Chen, Kanj 및 Xia 2006
^ Grohe (1999년)
^ Buss, Jonathan F; Islam, Tarique (2006). "Simplifying the weft hierarchy". Theoretical Computer Science. 351 (3): 303–313. doi:10.1016/j.tcs.2005.10.002.
^ Flum & Grohe (2006), 39페이지.

레퍼런스

Chen, Jianer; Kanj, Iyad A.; Xia, Ge (2006). Improved Parameterized Upper Bounds for Vertex Cover. MFCS 2006. Lecture Notes in Computer Science. Vol. 4162. pp. 238–249. CiteSeerX 10.1.1.432.831. doi:10.1007/11821069_21. ISBN 978-3-540-37791-7.
Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015). Parameterized Algorithms. Springer. p. 555. ISBN 978-3-319-21274-6.
Downey, Rod G.; Fellows, Michael R. (1999). Parameterized Complexity. Springer. ISBN 978-0-387-94883-6.
Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. ISBN 978-3-540-29952-3.
Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (2019). Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press. p. 528. doi:10.1017/9781107415157. ISBN 978-1107057760.
Niedermeier, Rolf (2006). Invitation to Fixed-Parameter Algorithms. Oxford University Press. ISBN 978-0-19-856607-6. Archived from the original on 2008-09-24.
Grohe, Martin (1999). "Descriptive and Parameterized Complexity". Computer Science Logic. Lecture Notes in Computer Science. Vol. 1683. Springer Berlin Heidelberg. pp. 14–31. CiteSeerX 10.1.1.25.9250. doi:10.1007/3-540-48168-0_3. ISBN 978-3-540-66536-6.
컴퓨터 저널제5권, 넘버 1 및 3(2008)컴퓨터 저널파라미터화된 복잡성에 관한 특집 이중호에서는 15개의 설문조사 기사, 서평, 게스트 에디터 R의 서문이 수록되어 있습니다.다우니, M. 펠로우, M. 랭스턴.

외부 링크

[1] Chen, Kanj 및 Xia 2006

[2] Grohe (1999년)

[3] Buss, Jonathan F; Islam, Tarique (2006). "Simplifying the weft hierarchy". Theoretical Computer Science. 351 (3): 303–313. doi:10.1016/j.tcs.2005.10.002.

[FOOTNOTEFlumGrohe200639-4] Flum & Grohe (2006), 39페이지.

[1]

[2]

[3]

[4]

Search