고정 매개변수 추적 가능 알고리즘이 존재하지 않는 NP 하드 문제가 있습니까?

https://cs.stackexchange.com/questions/129801

29-09-2020
|

문제

질문

매개변수를 추가할 수 있는 NP-하드 문제가 있습니까?¹ "자연"을 만들기 위해² FPT 알고리즘이 존재하지 않는 매개변수화된 문제입니까?

NP-하드 문제는 일반적으로 예 또는 아니요 대답이 있는 질문이기 때문에 매개변수 추가가 필요합니다. 일부 매개변수를 제한하려면 어떤 매개변수를 지정해야 합니다(비록 다음과 같더라도). $k$-채색에는 이미 분명한 것이 있을 수 있습니다. 따라서 "어떤 매개변수를 지정하는 것"이 제한되어 문제에 "매개변수를 추가하는 것"이 됩니다.더 자세한 설명은 Discrete Lizard의 답변에 포함되어 있습니다.
나는 이 질문에 대한 첫 번째 의심에서 논의한 것처럼 Natural이 "사소한" 매개변수화를 배제하려고 한다고 생각합니다.Discrete Lizard의 답변에 더 자세한 설명이 포함되어 있습니다.

의심

전체 문제를 항상 "채우기"하는 것이 가능하기 때문에 이는 사소한 질문일 수 있습니다. $f(k_1,k_2,..,k_m)$ ~의 일부 $f(k_1,k_2,..,k_m)n^c$ 알고리즘을 설정하는 동안 $n=c'$ 어디 $c'$ 임의의 상수입니다.그러나 아마도 FPT의 정확한 정의는 FPT 개념의 그러한 (남용) 사용을 방지할 것입니다.

plop의 의견에 따르면 실제로 "모든"(제대로 잘 제기된 문제라고 가정) 문제를 매개변수화하는 간단한 방법이 존재합니다. 즉 매개변수화는 fpt입니다.이러한 매개변수화는 내가 설명하는 언어를 사용합니다. 여기.그러한 "사소한"(난이도가 아닌 질문의 관점에서) 매개변수화는 무시되도록 의도되었습니다.따라서 Discrete lizard의 "말"은 다음과 같습니다.중요하지 않은 매개변수 범위가 의도되었습니다.

해결책

여기서 질문을 할 때는 약간 주의를 기울여야 합니다.NP-하드 문제는 결정 문제인 반면 FPT 알고리즘은 해결 문제입니다. 매개변수화된 결정이나 검색 문제.그래서 질문의 형식이 약간 잘못되었습니다.그러나 아마도 당신이 묻고 싶은 질문은 다음과 같습니다.

매개변수를 추가할 수 있는 NP-하드 문제가 있습니까?¹ "자연"을 만들기 위해² FPT 알고리즘이 존재하지 않는 매개변수화된 문제입니까?

정답은 (무조건!) 예.

우선, 고정된 매개변수 다루기 쉬운 알고리즘을 통해 해결 가능한 문제 클래스인 FPT는 다항식 시간 알고리즘으로 해결될 수 있는 "슬라이스별 다항식" 매개변수화된 문제 클래스인 XP의 고유 하위 집합이라는 점에 유의하세요. 매개변수가 고정된 경우.다시 말해서: $\mathrm{FPT} \subsetneq \mathrm{XP}$.(내 출처가 유일한 정당화로 제시한 "표준 대각화"로는 증거를 제공할 수 없음을 고백해야 합니다.아마도 복잡성 이론가가 나를 도와줄 수 있을 것입니다)

다음으로, XP의 적어도 하나의 문제는 FPT 알고리즘으로 해결될 수 없으므로 모든 XP 하드(FPT 감소 의미에서) 문제는 FPT 알고리즘으로 해결될 수 없습니다.

"증명된 난치성:다우니 앤 펠로우즈의 The Class XP' 매개변수화된 복잡성의 기본, 그들은 그들이 부르는 것을 보여줌으로써 논증을 완성합니다. 조약돌 게임 문제 적어도 PSPACE 하드("매개변수 제거" 후)로 알려진 문제를 "재해석"하여 XP 하드이므로 확실히 NP 하드입니다.자세한 내용은 해당 도서 장을 참조하세요.

이 결과는 나에게도 매우 놀랐다는 점을 덧붙이고 싶다. 현실적인 문제를 해결하려면 온갖 종류의 추측이 필요합니다($P eqNP$, ETH, SETH, 3-SUM 등)이지만 이 결과는 어떤 추측과도 무관한 실제 사실입니다.

_{1:명확히 하자면, "매개변수 추가"란 NP-하드 문제가 주어진다는 뜻입니다. $L\하위 집합\시그마^*$, 매개변수화된 문제 정의 $L'\subseteq \Sigma^* imes \mathbb{N}$ ~처럼 $L':= \{\langle x, k
angle \mid f(x)=k\}$ 어떤 기능을 위해 $f :\시그마^*
ightarrow \mathbb{N}$.이는 추가 매개변수가 입력의 속성을 측정한다는 직관적인 아이디어를 포착합니다.
2:1의 정의에서는 여전히 다음과 같은 함수를 사용하여 모든 종류의 이상한 매개변수화를 허용합니다. $f(x)\equiv 1$.이상적으로는 $f$ 인스턴스에 대해 의미 있는 것을 측정하지만 공식화하기는 어려워 보입니다."부자연스러운" 매개변수화를 모두 제거하는 다른 형식화도 생각할 수 없었습니다.그래서 나는 대신 Downey and Fellows의 책에서 "자연 매개변수화된 문제"라는 비공식적 개념을 복사하겠습니다.}

다른 팁

나는 예라고 말할 것이지만, p $ \ neq $ np의 조건을 수락해야합니다. $ k $ - Coloring, $ k $ 두 개의 연결된 정점이 같은 색상이 없도록 색상이 동일합니다. 분명히, 우리는 $ k $ - 컬러링으로 3 색을 줄일 수 있습니다.

$ k $ - Coloring은 FPT에 있으며 $ F ($ F) 에서이 문제를 해결하는 알고리즘이 있습니다. k) \ cdot n ^ {o (1)} $ . $ k= 3 $ 을 설정 한 다음 P $ \ neq $ np. 분명히, p $ \ neq $ np, $ k $ 의 FPT 알고리즘은 없습니다. .

절대적으로 존재할 수 없다는 의미에서 더 엄격하게 뭔가를 찾고 있다면, 그러한 문제가 발견되었는지 확실하지는 않습니다.

또 다른 옵션은 스탠자의 해결책과 개별 도마뱀 솔루션보다 훨씬 약하고, 기하 급수적 인 시간 가설 (eth)을 가정하는 것입니다. eth 가정 $ fpt \ neq w [1] $ (또는 FPT $ \ neq $ w [1]을 직접 가정).

$ \ neq $ w [1] 하나는 NO (비 사소한) 매개 변수화 $ KD $ a w [1] - 하드 문제는 FPT입니다. NP-HARD *가 $ k-clique $ 에있는 AW [1]의 예는 $ KD $ w [1] - 가정 FPT $ \ neq $ w [1], 이것은 (비 - 사소한) 매개 변수화 $ kd $ np-hard 문제 $ K-Clique $ 은 FPT가 아닙니다. 즉, FPT $ \ neq $ w [1]에 FPT가 아닌 NP 하드 문제가 있습니다.

의사 결정 문제 ( $ k $ ) - Clique 는 NP-Complete 입니다. 따라서 아래 그림과 같이 np-hard이기도합니다.

면책 조항

나는이 주장을 제시하지 않았으며 기본적으로 이산 도마뱀의 의견이며, " $ a $ 이 존재하는 것과 거의 같습니다. ? " 와: " $ b $ 이 존재한다고 가정합니다. 오, $ a $ 이됩니다. $ b $ , $ b $ 이 존재한다고 가정 한 후 $ a $ , 그렇습니다. $ a $ (주석의 이산 도마뱀에 의해 설명되는 것처럼 설명합니다).

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 cs.stackexchange