Existe-t-il un problème de NP-dur pour lequel aucun algorithme de paramètres à paramètres fixe n'existe?

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

29-09-2020
|

Question

Y a-t-il un problème de NP-dur pour lequel nous pouvons ajouter un paramètre ^{1 pour créer un problème "naturel" ^{2 paramétré pour lequel aucun algorithme FPT n'existe?}}

L'ajout d'un paramètre est nécessaire car un problème de NP-dur est normalement une question avec une réponse Oui ou Non, si vous souhaitez limiter certains paramètres, vous devez spécifier lequel (même si quelque chose comme quelque chose comme $ K $ -Coloring peut être déjà évident déjà), de sorte que" spécifier quel paramètre "est limitant, on" ajout d'un paramètre "au problème. Une description plus détaillée est incluse dans la réponse par lézard discret.
Je pense que Natural essaie d'exclure les paramétrages "triviaux" comme je discute de mon premier doute dans cette question. Encore une fois une description plus détaillée est incluse dans la réponse par lézard discret.

Doute

Cela pourrait être une question triviale car il est peut-être possible de toujours "supporter" tout le problème de la $ f (k_1, k_2, .., k_m) $ partie de la $ f (k_1, k_2, .., k_m) n ^ c d $ algorithme tandis que réglage N= N= C '$ où $ C' $ est une constante arbitraire. Mais peut-être que la définition exacte du FPT empêche une telle utilisation du concept de FPT.

Basé sur le commentaire de Plop, il existe en effet un moyen trivial de paramétrer "tout" (je suppose tout problème correctement posé), de sorte que son paramétrage soit FPT. Ces paramétrisations utilisent des langues, que je suppose être ce qui est décrit ici . Un tel "trivial" (à la lumière de la question, pas à la lumière de la difficulté) Le paramétrage est destiné à être ignoré. Donc, dans les "mots" du lézard discret: une gamme de paramètres non triviale est (sont) destinées.

La solution

Vous devez être un peu prudent avec votre question ici. Notez qu'un problème de décision du NP-dur est un problème de décision, tandis que les algorithmes FPT résolvent paramétrisés problèmes de recherche ou de recherche. La question est donc un peu mal formée. Cependant, je pense que la question que vous avez probablement destinée à demander est:

Y a-t-il un problème de NP-dur pour lequel nous pouvons ajouter un paramètre ^{1 pour créer un problème "naturel" ^{2 paramétré pour lequel aucun algorithme FPT n'existe?}}

à laquelle la réponse est (inconditionnellement!) oui .

Tout d'abord, notez que FPT, la classe de problèmes résolvable via un algorithme de paramètres fixe, est un sous-ensemble approprié de XP, la classe des "polynomiels de la tranche" des problèmes paramétrés pouvant être résolus par un polynôme algorithme de temps si le paramètre est corrigé. En d'autres termes: $ \ MATHRM {FPT} \ SOUSETNEQ \ MATHRM {XP} $ . (Je dois avouer que je ne suis pas en mesure de fournir la preuve par «la diagonalisation standard» que ma source offre comme la seule justification. Peut-être un théoricien de la complexité peut m'aider ici)

Ensuite, notez que, depuis au moins un problème dans XP, ne peut pas être résolu par un problème de FPT-HARD (dans le sens des réductions de la FPT), ne peut pas être résolu par un algorithme FPT.

dans le chapitre "Intractabilité prouvable: la classe XP" dans les de la complexité paramétrisée , ils complètent l'argument en montrant que ce qu'ils appellent le problème de jeu de galets est XP-HARD par "réinterprétation" un problème connu pour être au moins pSpace-dur (après "retirer le paramètre"), donc certainement np-dur. Voir ce chapitre de livre pour plus de détails.

Permettez-moi d'ajouter que ce résultat m'a également été très surprenant, car pour la plupart des problèmes pratiques , nous avons besoin d'al peu de conjectures ( $ p \ NEQ NP $ , ETH, SETH, 3-SUM, etc.), mais ce résultat est un fait réel indépendant de toute conjecture.

_{1: Pour clarifier, en "Ajout d'un paramètre", je veux dire compte tenu d'un problème de la NP-dur $ l \ sous -éréq \ sigma ^ * $ , Définir un problème paramétré $ L '\ SOUSETEQ \ SIGMA ^ * \ TIMES \ MATHBB {N} $ AS $ L':={\ utilgne x, k \ rang \ mid f (x)= k \} $ pour une fonction $ f: \ sigma ^ \ rightarrow \ mathbb { N} $ . Cela capture l'idée intuitive que le paramètre supplémentaire mesure une propriété de l'entrée.

2: La définition en 1 permet toujours toutes sortes de paramétrisations étranges avec des fonctions telles que $ f (x) \ equiv 1 $ . Idéalement, nous aurions besoin de $ f $ pour mesurer quelque chose de significatif sur l'instance, mais cela semble difficile à formaliser. Je ne pouvais penser à aucune autre formalisation qui supprime toutes les paramétrisations "non naturelles" non plus. Donc, je vais plutôt copier la notion informelle des "problèmes paramétrés naturels" du livre de Downey et des Fellows.}

Autres conseils

Je dirais oui, mais vous devez accepter la condition que p $ \ neq $ np. Prenez $ K $ -Coloring, où nous souhaitons déterminer si un graphique peut être coloré avec $ k $ Des couleurs telles que deux sommets connectés n'ont pas la même couleur. Clairement, nous pouvons réduire la coloration de la coloration à $ K $ -Coloring.

Supposons $ k $ -coloring est dans FPT, puis il existe un algorithme qui résout ce problème dans $ f ( k) \ CDOT n ^ {o (1)} $ . Si nous définissons $ K= 3 $ , nous obtenons un algorithme de temps polynomial, et donc 3 colorants peuvent être résolus en polynôme-temporel, sauf si p $ \ neq $ np. Évidemment, si p $ \ neq $ np, il n'y a pas d'algorithme FPT pour $ k $ -coloring .

Si vous recherchez quelque chose de plus strictement dans le sens où il ne peut absolument pas exister, je ne suis pas sûr de savoir si un tel problème a été trouvé.

Peut-être une autre option, de manière significative plus faible que la solution de Stanja et la solution de lézards discret, assume l'hypothèse de temps exponentielle (ETH). Eth suppose $ FPT \ neq w [1] $ (ou supposez simplement FPT $ \ neq $ w [1] directement).

SO avec FPT $ \ NEQ $ W [1] L'on suppose no (non trivial) Paramétrage $ KD $ d'un problème W [1] est FPT. Un exemple d'aw [1] problème dur qui est np-dur * est $ k-clique $ , il existe donc un problème AW [1] -Hard - un problème qui est un NP -Le problème. Etant donné que (non trivial) paramétrage $ kd $ w [1] -hard problèmes ne sont pas (dans) FPT avec Assomption FPT $ \ neq $ w [1], ce moyen, tout paramétrage (non trivial) $ kd $ de NP-HARD Problème $ k-clique $ n'est pas FPT. Cela signifie que si FPT $ \ NEQ $ W [1], il existe un problème de la NP-dur qui n'est pas FPT.

le problème de décision ( $ k $ ) - clique NP-Complete est donc aussi np-dur que l'image ci-dessous montre:

Disclaimer

Je n'ai pas trouvé cet argument, c'est fondamentalement le commentaire du lézard discret, et c'est presque comme répondre à la question: "Est-ce que $ a $ ? " avec: "Je suppose que $ b $ existe, oh il arrive d'être une $ a $ $ B $ , et depuis que j'ai supposé $ B $ existe, alors il doit également exister une classe $ A $ , donc oui il existe une $ a $ . (Comme il est également expliqué par le lézard discret dans les commentaires)

Licencié sous: CC-BY-SA avec attribution

Non affilié à cs.stackexchange