Esiste un problema NP-difficile per il quale non esiste un algoritmo trattabile a parametri fissi?

Question

Domanda

Esiste un problema NP-difficile per il quale possiamo aggiungere un parametro¹ creare un ambiente "naturale"² problema parametrizzato per il quale non esiste un algoritmo FPT?

1. L'aggiunta di un parametro è necessaria perché un problema NP-difficile è normalmente solo una domanda con una risposta sì o no, se vuoi limitare alcuni parametri devi specificare quale (anche se qualcosa come $k$-La colorazione potrebbe già averne una ovvia), quindi con "specificare quale parametro" si sta limitando, si sta "aggiungendo un parametro" al problema.Una descrizione più dettagliata è inclusa nella risposta di Discrete Lizard.
2. Penso che Natural cerchi di escludere parametrizzazioni "banali" come discuto nel mio primo dubbio in questa domanda.Anche in questo caso una descrizione più dettagliata è inclusa nella risposta di Discrete Lizard.

Dubbio

0. Potrebbe essere una domanda banale in quanto forse è possibile sempre "riempire" l'intero problema all'interno del file $f(k_1,k_2,..,k_m)$ parte di $f(k_1,k_2,..,k_m)n^c$ algoritmo durante l'impostazione $n=c'$ Dove $c'$ è una costante arbitraria.Ma forse l’esatta definizione di PLT impedisce tale (ab)uso del concetto di PLT.

Sulla base del commento di plop esiste infatti un modo banale per parametrizzare "qualsiasi" problema (presumo qualsiasi problema adeguatamente ben posto), in modo tale che la sua parametrizzazione sia fpt.Tali parametrizzazioni utilizzano linguaggi, che presumo siano quelli descritti Qui.Una parametrizzazione così "banale" (alla luce della domanda, non alla luce delle difficoltà) è destinata ad essere ignorata.Quindi nelle "parole" di Discrete Lizard:sono previsti intervalli di parametri non banali.

Answer 1

Devi stare un po' attento con la tua domanda qui.Si noti che un problema NP-difficile è un problema decisionale, mentre gli algoritmi FPT lo risolvono parametrizzato problemi decisionali o di ricerca.Quindi la domanda è un po’ mal formulata.Tuttavia, penso che la domanda che probabilmente volevi porre sia:

Esiste un problema NP-difficile per il quale possiamo aggiungere un parametro¹ creare un ambiente "naturale"² problema parametrizzato per il quale non esiste un algoritmo FPT?

Alla quale la risposta è (incondizionatamente!) SÌ.

Prima di tutto, si noti che FPT, la classe di problemi che sono risolvibili tramite un algoritmo trattabile a parametri fissi, è un sottoinsieme proprio di XP, la classe di problemi parametrizzati "polinomio-slice" che possono essere risolti da un algoritmo tempo-polinomiale se il parametro è fisso.In altre parole: $\mathrm{FPT} \subsetneq \mathrm{XP}$.(Devo confessare che non sono in grado di fornire la prova mediante la "diagonalizzazione standard" che la mia fonte offre come unica giustificazione.Forse un teorico della complessità può aiutarmi qui)

Successivamente, si noti che poiché almeno un problema in XP non può essere risolto da un algoritmo FPT, qualsiasi problema XP-hard (nel senso di riduzioni FPT) non può essere risolto da un algoritmo FPT.

Nel capitolo "Intrattabilità dimostrabile:La Classe XP" in Downey and Fellows' Fondamenti di complessità parametrizzata, completano l'argomentazione mostrando che ciò che chiamano il PROBLEMA DEL GIOCO DEI CIOTTOLI è XP-hard "reinterpretando" un problema noto per essere almeno PSPACE-hard (dopo aver "rimosso il parametro"), quindi certamente NP-hard.Vedi il capitolo del libro per maggiori dettagli.

---

Aggiungo che questo risultato è stato molto sorprendente anche per me, perché per la maggior parte pratico problemi, abbiamo bisogno di ogni sorta di congetture ($P eq NP$, ETH, SETH, 3-SUM, ecc.), ma questo risultato è un fatto reale e indipendente da qualsiasi congettura.

---

_{1:Per chiarire, per "aggiungere un parametro", intendo dato un problema NP-difficile $L\subseteq \Sigma^*$, definire un problema parametrizzato $L'\subseteq \Sigma^* imes \mathbb{N}$ COME $L':= \{\langle x, k angle \mid f(x)=k\}$ per qualche funzione $f:\Sigma^* ightarrow \mathbb{N}$.Ciò cattura l'idea intuitiva che il parametro aggiuntivo misura una proprietà dell'input.
2:La definizione in 1 consente ancora tutti i tipi di strane parametrizzazioni con funzioni come $f(x)\equiv 1$.Idealmente, avremmo bisogno di $f$ per misurare qualcosa di significativo nell'istanza, ma sembra difficile da formalizzare.Non potrei nemmeno pensare a nessun'altra formalizzazione che rimuova tutte le parametrizzazioni "innaturali".Quindi copierò invece la nozione informale di "problemi parametrici naturali" dal libro di Downey e Fellows.}

Answer 2

Direi di Sì, ma è necessario accettare la condizione che p $ \ neq $ np. Prendere $ k $ -Coloring, dove vogliamo determinare se un grafico può essere colorato con $ k $ Colori tali che due vertici collegati non hanno lo stesso colore. Chiaramente, possiamo ridurre 3-colorazione a $ k $ -Coloring.

Supponiamo $ k $ -Coloring è in FPT, quindi esiste un algoritmo che risolve questo problema in $ f ( k) \ cdot n ^ {o (1)} $ . Se abbiamo impostato $ k= 3 $ , quindi otteniamo un algoritmo polinomiale, e quindi 3-coloring può essere risolto in tempo polinomiale a meno che p $ \ neq $ np. Ovviamente, se p $ \ neq $ np, quindi non esiste un algoritmo FPT per $ k $ -Coloring .

Se stai cercando qualcosa di più strettamente nel senso che non può assolutamente esistere, allora non sono sicuro se è stato trovato un tale problema.

Answer 3

Forse un'altra opzione, significativamente più debole della soluzione della soluzione di Stanja e della soluzione di lucertole discrete, sta assumendo l'ipotesi dell'ora esponenziale (ETH). Eth presuppone $ fpt \ neq w [1] $ (o semplicemente assumere fpt $ \ neq $ w direttamente [1]).

SO con FPT $ \ neq $ w [1] Uno assume alcun parametrizzazione (non banale) parametrizzazione $ kd $ di un problema [1] -Hard è FPT. Un esempio di AW [1] Problema difficile che è np-hard * è $ k-clique $ , quindi esiste aw [1] -hard problema che è un NP -hard problema. Dal momento che (non banale) parametrizzazione $ kd $ w [1] -hard I problemi non sono (in) fpt con l'assunzione fpt $ \ neq $ w [1], questo significa, qualsiasi parametrizzazione (non banale) $ kd $ di NP-Hard problem $ k-clique $ non è FPT. Ciò significa, se fpt $ \ neq $ w [1], esiste un problema duro NP che non è FPT.

.
• il problema decisione ( $ k $ ) - clique è NP-Completa , quindi, è anche NP-HARDS quando l'immagine qui sotto mostra:

Disclaimer

Non ho trovato questa argomentazione, è fondamentalmente il commento della lucertola discreta, ed è quasi come rispondere alla domanda: "Esegue $ A $ esistono ? " con: "Suppongo che $ B $ esiste, oh accade essere un $ a $ che è in set $ B $ , e da quando ho assunto $ B $ esiste, quindi ci deve esistere anche una classe $ A $ , quindi sì esiste una $ a $ . (Come è anche spiegato da una lucertola discreta nei commenti)