매개 변수화 된 복잡성에서, ⊆ W [ 2 ] ⊆ … ⊆ W [ P ] . 각각의 격리가 적절하다고 추측된다.
FPT⊆W[1]⊆W[2]
⊆…⊆W[P]
만약 다음 P = W [ P ] .
FPT=W[P]P=W[P]
그러나 그것은 그것을 따릅니다
- 만약 다음 F P T = W [ P ] ? 또는
FPT=W[1] FPT=W[P] - 만약 다음 (일부 t 용) F P T = W [ P ] ?
W[t−1]=W[t] FPT=W[P]
답변
이 질문은 답이 (아는 한) 여전히 “모르는”것이므로 까다 롭습니다.
이것에 약간의 무게를 더하기 위해 Flum & Grohe [1]는 공개적인 문제를 주었다 (p. 164) :
- 인 가정하에 엄격한 -hierarchy F P T ≠ W [ P ] ?
W FPT≠W[P]- 들면 , 동등하지 W [ t ] = W [ t + 1 ] 의미 W [ t ] = W [ t + 2 ] ?
t≥1 W[t]=W[t+1] W[t]=W[t+2]
또한 다우니와 펠로우의 최근 논문 [2]에서 가장 강력한 주장은 다음과 같다 (p. 521).
더 미묘한 가설은 계층이 적절하고 특히 W [ 1 ] ≠ W [ 2 ]라는 것 입니다.
WW[1]≠W[2]
“그렇지 않으면 계층 구조가 붕괴 될 것”또는 이와 유사한 행을 따라 다음 (또는 나중에) 진술은 없습니다 .
W이것은 또한 앞에옵니다 :
약한 가설은 일부 경우
t
F P T ≠ W [ t ] 일 수있다.
FPT≠W[t]
계층에 다른 영향을 미치지 않으면 서 일 수 있음을 암시합니다 .
FPT=W[t−1]참고 문헌 :
- J. Flum and M. Grohe, “매개 변수화 된 복잡성 이론”, Springer, 2006.
- R. Downey와 M. Fellows, “매개 변수화 된 복잡성의 기초”, Springer, 2014.