Existe-t-il des problèmes NP-complets avec les solutions de temps attendu polynomiales?

24

Existe-t-il des problèmes NP-complets pour lesquels un algorithme est connu que le temps d'exécution attendu est polynomial (pour une distribution sensible sur les instances)?

Sinon, existe-t-il des problèmes pour lesquels l'existence d'un tel algorithme a été établie?

Ou l'existence d'un tel algorithme implique-t-elle l'existence d'un algorithme de temps polynomial déterministe?

cc.complexity-theory np-hardness Steve Kroon
la source

6

Je ne comprends pas très bien quelle est la question. Demandez-vous des résultats moyens pour des problèmes NP-durs ou demandez-vous si nous pouvons résoudre des problèmes NP-durs dans le pire des cas en temps polynomial attendu?

Moritz

2

Qu'entendez-vous par «durée de fonctionnement prévue»? Prenez-vous l'espérance sur une distribution aléatoire d'entrées (comme la plupart des réponses semblent le penser), ou sur la distribution de bits aléatoires utilisée par l'algorithme (la signification habituelle pour les algorithmes randomisés), ou les deux?

Jeffε

@Moritz: Je demande des résultats de cas moyens pour des problèmes NP-difficiles. Résoudre des problèmes NP-difficiles dans le pire des cas dans le temps polynomial attendu semble être un résultat encore plus fort pour moi, donc je serais également intéressé par de tels résultats. @JeffE Je parle du temps prévu par rapport à la distribution sur les instances. Si l'algorithme est randomisé, on prendrait également l'attente sur les bits aléatoires. Mais ma question ne concerne pas principalement l'algorithme randomisé.

Steve Kroon

3

Une technique de rembourrage simple vous permet de les construire à partir de n'importe quel problème.

Supposons que est un langage -Complete qui nécessite temps pour résoudre. Ensuite , laissez soit Alors est résolu comme suit: un algorithme vérifie en temps linéaire si une chaîne d'entrée a un nombre pair de caractères dont les premiers sont . Sinon, il rejette; sinon il résout . Si est dessiné uniformément au hasard, le temps prévu pour résoudre est $L$ $NP$ $O(2^{n})$ $K$

K = {1^{n} x | ‖ x ‖ = n and x \in L}

$K=\{1^nx\ |\ \|x\|=n \text{ and }x\in L\}$

K

$K$

n

$n$

1^{n}

$1^n$

x \overset{?}{\in} L

$x\overset{?}{\in}L$

y \in_{R} {0, 1}^{2 n}

$y\in_R \{0,1\}^{2n}$

y \overset{?}{\in} K

$y\overset{?}{\in}K$

\frac{1}{2^{2 n}} (2^{n} \cdot 2^{n} + (2^{2 n} - 2^{n}) O (n)) = 1 + (1 - \frac{1}{2^{n}}) O (n) \in O (n) .

$\frac{1}{2^{2n}}\big(2^n\cdot 2^n+(2^{2n}-2^n)O(n)\big) = 1+(1-\frac{1}{2^n})O(n)\in O(n).$

$K$ est -Complet. Une réduction de est: $NP$ $L$

x \in {0, 1}^{n} \mapsto 1^{n} X

$x\in \{0,1\}^n \mapsto 1^nx$

Lieuwe Vinkhuijzen
la source

13

Il existe un algorithme de temps polynomial pour trouver des cycles hamiltoniens sur des graphiques aléatoires, qui réussit asymptotiquement avec la même probabilité qu'un cycle hamiltonien existe. Bien sûr, ce problème est NP-difficile dans le pire des cas.

Ils montrent également qu'un algorithme de programmation dynamique qui est toujours garanti de trouver un cycle hamiltonien, s'il existe, a un temps d'exécution polynomial attendu, si la distribution d'entrée est uniformément aléatoire sur l'ensemble des graphes de sommet. $n$

Référence: "Un algorithme pour trouver des cycles de Hamilton dans des graphes aléatoires"

Bollobas, Fenner, Frise

http://portal.acm.org/citation.cfm?id=22145.22193

Aaron Roth
la source

10

Concernant votre dernière question sur la question de savoir si l'existence d'un bon algorithme de cas moyen impliquerait l'existence d'un bon algorithme de pire cas: il s'agit d'une question ouverte majeure qui intéresse particulièrement les cryptographes. La cryptographie nécessite des problèmes qui sont durs en moyenne, mais les cryptographes aimeraient fonder leurs constructions sur les hypothèses minimales possibles, il est donc très intéressant de trouver des problèmes où la dureté moyenne est prouvablement égale à la dureté la plus défavorable.

Plusieurs problèmes de réseau sont connus pour avoir des réductions allant du pire au cas moyen. Voir, par exemple, Generating hard instances of lattice problems by Ajtai, and a survey article by Micciancio.

Ian
la source

9

$n$ $n$

Référence:

Alexander D. Scott et Gregory B. Sorkin. Résolution d'instances aléatoires clairsemées de Max Cut et Max 2-CSP en temps linéaire attendu. Peigne. Probab. Comput, 15 (1-2):. 281-315, 2006. Preprint

Serge Gaspers
la source

2

Θ (n)

$\Theta(n)$

G (n, c / n)

$G(n,c/n)$

@Bart: J'ai peut-être mal compris la question. Je prétends que Max 2-CSP avec un nombre linéaire de clauses est NP-difficile, mais qu'il existe un algorithme avec un temps linéaire attendu pour résoudre ce problème pour les instances aléatoires.

Serge Gaspers

Fondamentalement, si je comprends bien votre argument, vous dites que Max 2-CSP équipé de la distribution G (n, c / n) sur les graphiques sous-jacents peut être résolu dans le temps linéaire attendu. Je suis d'accord avec Bart en ce que la distribution ne me semble pas entièrement "sensée" ou "naturelle", mais je pense qu'elle répond adéquatement à ma question.

Steve Kroon

@Steve: Je suis d'accord.

Serge Gaspers

7

Cela ne répond pas complètement à votre question, mais pour un sondage des résultats sur des instances aléatoires de 3-SAT, vous pouvez le voir: www.math.cmu.edu/~adf/research/rand-sat-algs.pdf

Habituellement, il est difficile de définir ce que signifie réellement «distrubution sensible». Vous pouvez suivre ce lien pour en savoir plus à ce sujet dans l'enquête "Complexité en temps moyen" de Bogdanov et Trevisan: http://arxiv.org/abs/cs/0606037 .

Grigory Yaroslavtsev
la source

Merci pour les liens. Malheureusement, les résultats "à forte probabilité" du papier 3-SAT ne sont pas assez forts (pour autant que je puisse voir) pour affirmer ma requête. Je suis d'accord que la "distribution raisonnable" peut être velue. En cela, je préférerais que la distribution ne soit pas choisie de manière évidente afin que "l'espace d'instance efficace" ne se résume pas simplement à un problème connu pour être en P.

Steve Kroon

5

"Coloration de graphiques aléatoires en temps polynomial prévu" par Amin Coja-Oghlan et Anusch Taraz

$G \in G(n, p)$ $p < 1.01/n$ $O(√np)$

http://www.springerlink.com/content/87c17d4dacbrc0ma/

Joel Rybicki
la source

Existe-t-il des problèmes NP-complets avec les solutions de temps attendu polynomiales?

Réponses: