«Objet accessible» est-il vraiment un problème NP-complet?

Je lisais cet article où les auteurs expliquent le théorème 1, qui déclare que "l'objet accessible" (tel que défini dans l'article) est NP-complet. Cependant, ils prouvent la réduction dans une seule direction, c'est-à-dire de 2P1N SAT à l'objet accessible. Cela prouve seulement que le problème est NP-difficile; n'avons-nous pas besoin de prouver la direction inverse (2P1N vers l'objet accessible) pour prouver l'exhaustivité de NP?

complexity-theory np-complete np-hard satisfiability Infini
la source

Les auteurs n'ont pas prouvé que le problème réside dans le NP, ils ont seulement prétendu qu'il le fait (et qu'il est facile de le prouver). Ils ont une dureté NP prouvée.

Lézard discret

Je veux juste que vous sachiez que le symbole l'est \in, non \epsilon.

Alice Ryhl

Réponses:

Un problème est NP-complet si: $P$

$P$ est NP-dur et
$P \in \textbf{NP}$ .

Les auteurs donnent une preuve de l'article numéro 1. L'article numéro 2 est probablement apparent (et devrait être clair pour le public de l'article). Pour la preuve de l'article numéro 1, vous avez seulement besoin d'une réduction (plusieurs) d'un problème NP-complet (par exemple, SAT) à ; il n'est pas nécessaire de construire une réduction en sens inverse. $P$

dkaeae
la source

Dans le cas où quelqu'un est toujours confus, 2 est trivial car être en NP signifie que vous pouvez rapidement (temps polynomial) vérifier une solution au problème. Ici, une solution peut être vérifiée en effectuant simplement les échanges comme indiqué dans la solution et en vérifiant que vous atteignez l'objet souhaité.

Steven Waterman

@StevenLowes La seule chose que vous auriez encore à vérifier est que le nombre de swaps requis est polynomial. Cela aussi n'est pas si difficile à voir, comme je l'explique dans ma réponse.

Lézard discret

J'avais mal lu le papier et j'avais supposé qu'il n'était pas possible qu'une séquence nécessite plus que N swaps - vous avez raison :)

Steven Waterman

@StevenLowes: Eh bien, il vaudrait aussi mieux être (exprimable comme) un problème de décision. Il y a des problèmes NP-difficiles qui ne sont pas du tout des problèmes de décision, qui ne seront évidemment pas dans NP, même s'ils sont faciles à "vérifier".

Kevin

Les auteurs affirment qu'il est facile de montrer que le problème réside dans le NP. Pour prouver cette affirmation, prenez une séquence d'échanges qui mène à un état comme témoin que l'état est accessible. Compte tenu d'une telle séquence de taille polynomiale, on peut vérifier en temps polynomial que l'état est bien accessible en effectuant les swaps.

Ce qui reste à montrer, c'est qu'il existe une séquence de swaps qui a une taille polynomiale. Notez que puisque chaque agent a des préférences strictes et n'échangera que s'il peut faire un échange qui lui donne un meilleur objet, chaque agent peut échanger au plus $n$ fois. Comme il y a tout au plus $n$ agents, chaque séquence de swaps a au plus $n^2$ swaps.

Je pense que s'il y avait des préférences non strictes, il pourrait être possible que certains éléments traversent de longs cycles pour atteindre certains états, et qu'il existe en particulier des états où toutes les séquences de swaps ont une taille exponentielle. Cependant, je ne peux pas penser à un exemple immédiat d'un tel problème. À tout le moins, il n'est plus «facile» de montrer que le problème des préférences non strictes est dans NP.

Lézard discret
la source