La dureté monte en complexité informatique?

Le problème de bande passante minimum est de trouver un ordre des nœuds de graphe sur une ligne entière qui minimise la distance la plus grande entre deux nœuds adjacents quelconques. Une chenille est un arbre formé à partir de la trajectoire principale par la croissance de trajectoires dont les arêtes sont disjointes de plus en plus de partir de ses nœuds ( est appelée la longueur des cheveux). Le problème de bande passante minimale est en pour 2 chenilles mais complet pour 3 chenilles.$k$$k$$k$$P$$NP$

Voici un fait très intéressant: le problème de bande passante minimale peut être résolu en temps polynomial pour 1 chenille (longueur du cheveu au plus), mais il est complet pour les 1 chenilles cycliques (en chenille cyclique, un bord est ajouté pour relier les extrémités). du chemin principal). Ainsi, l'ajout d'un seul bord rend le problème complet.$NP$$NP$

Quel est l'exemple le plus frappant de saut de la dureté du problème où une petite variation d'instance d'entrée provoque un saut de complexité de la capacité de résolution polynomiale à la complétude ?$NP$

L'un des exemples les plus intéressants de sauts de dureté appliqués peut être observé dans le problème suivant:

Considérons un championnat de ligue de football avec équipes: le problème de savoir si une équipe donnée peut (encore) gagner la ligue est en P si, dans un match, l’équipe gagnante obtient 2 points, l’échec 0 et chaque équipe 1. point dans un match nul. Mais si nous changeons les règles pour que l’équipe gagnante obtienne 3 points, le même problème devient N P -hard.$n$$P$$NP$

Le résultat peut être généralisé pour toute règle de points pour chaque k > 2 et même pour les trois tours restants.$(0, 1, k)$$k > 2$

Source: «Théorie de la complexité» par Ingo Wegener ( http://portal.acm.org/citation.cfm?id=1076319 )

Cela répond à la question posée dans le titre de la question, mais pas à celle posée dans la question.

Un exemple choquant de dureté apparente découle de la question "Combien d'assignations satisfaisantes une formule plane a-t-elle, modulo ?" Cela a été largement considéré comme étant # P-dur, et il s’agit de "la plupart" des valeurs de n , mais si n est un entier de Mersenne (par exemple, n = 7 , car 7 est de forme 2 3 - 1 ), alors la réponse peut être calculé en temps polynomial.$n$$n$$n$$n=7$$2^3-1$

Cela a été découvert pour la première fois par Valiant dans son document révolutionnaire intitulé Algorithmes holographiques.

INDEPENDENT SET est NP-complet pour les graphes sans (croix, triangle) , mais peut être résolu en temps linéaire pour les graphes sans (chaise, triangle) . (Les graphes sans X sont ceux qui ne contiennent aucun graphe de X en tant que sous-graphe induit.)

chaise: triangle: croix:

Notez que la croix est obtenue à partir de la chaise en ajoutant un seul bord.

Je ne suis pas sûr d’accepter votre caractérisation selon laquelle l’ajout d’un seul bord à l’entrée rend le problème NP-complet, puisqu’il permet en fait d’ajouter un bord à chacune des innombrables instances d’entrée.

Voici un exemple de problème qui montre une nette dichotomie selon les lignes que vous suggérez.

Le problème de déterminer s'il existe un homomorphisme de graphe du graphe d'entrée G à un graphe de gabarit fixe H est dans P lorsque H est un graphe avec une boucle automatique ou un graphe sans boucle bipartite. Lorsque H n'est pas bipartite (ceci peut souvent être réalisé en ajoutant une seule arête), le problème devient NP-complet.

• P. Hell et J. Nešetřil, Complexité de la coloration H , J. Comb. Th. B 48 92-110, 1990. doi: 10.1016 / 0095-8956 (90) 90132-J

La clé ici est que la 2-coloration est en P (cela correspond à un homomorphisme à , le chemin sur 3 sommets), tandis que la 3-coloration est NP-complète (cela correspond à un homomorphisme à K 3 , le triangle).$P_3$$K_3$

Voici un autre exemple intéressant, soulevé dans la détection de sous-graphe induit:

Un thêta est un graphe dont les sommets non adjacents $x,y$ , trois chemins $P_1, P_2, P_3$ de $x$ à $y$ , où deux chemins quelconques induisent un cycle de longueur supérieure à 3.

Une pyramide est un graphe avec un sommet $x$ , un triangle $y_1,y_2,y_3$ et les chemins $P_i$ de $x$ à $y_i$ pour chaque $i=1,2,3$ , avec au plus un chemin de longueur un.

Enfin, un prisme est un graphique avec deux triangles $x_1,x_2,x_3$ et $y_1,y_2,y_3$ , et les chemins $P_i$ de $x_i$ à $y_i$ pour chaque $i=1,2,3$ .

Il est facile de décrire en chiffres:

Pour détecter la thêta et la pyramide induites, il est connu d’être en temps polynomial. (En fait, le meilleur algorithme connu pour thêta prend $O(n^{11})$ , et pour la pyramide, il faut $O(n^9)$ .) Mais pour détecter un prisme induit, le problème devient NP-difficile.

On peut voir " Détecter des sous-graphes induits " de Leveque, Lin, Maffray et Trotignon pour référence. La raison pour laquelle thêta et pyramide sont relativement faciles est liée au problème des "trois en un arbre", décrit dans " Le problème des trois en un " de Chudnovsky et Seymour.

euh ... je suis sûr que vous recherchez des exemples moins triviaux ... mais je tiens à souligner que le chiffre vs 3 a quelque chose de spécial . 2 - S A T à 3 - S A T , 2 - C O L vs 3 - C O L , etc. Intuitivement, je l' ai toujours pensé que c'était parce qu'un noeud avec au plus 2 bords peuvent former au plus une ligne, mais un nœud avec 3 arêtes peut former un arbre, lorsque nous passons de 2-3, nous obtenons une explosion combinatoire.$2$$3$$2-SAT$$3-SAT$$2-COL$$3-COL$

Je pense que parler de cas n’a pas beaucoup de sens. Nous pouvons parler de deux distributions d'instances d'entrée avec des difficultés différentes, mais ce serait plus intéressant s'il existe une relation entre la distribution ou entre les instances dans les distributions.

Nous pouvons considérer une famille paramétrée de distributions, puis parler de ce qui se passe lorsque nous modifions le paramètre. Vous pourriez être intéressé par ce qu'on appelle le phénomène de seuil , "lorsqu'un système subit un changement qualitatif rapide à la suite d'un petit changement dans un paramètre ...". Jetez un coup d’œil à cette enquête: Ehud Friedgut , «À la recherche de seuils précis », Algorithmes de structures aléatoires 26, 2005.

Je pense que l'un des exemples les plus frappants et les plus beaux est le k-SAT aléatoire avec densité de clause , la transition de phase est vraiment étonnante.$\Delta$

Inférant types pour les termes lambda est DEXPTIME-avec prénexe et de rang 2 systèmes de type polymorphes (lorsque le type quantificateurs sont imbriqués au plus un niveau profond), mais devient indécidable pour le rang 3 et plus. Étrange qu'un niveau d'imbrication supplémentaire puisse rendre un problème indécidable.

Trouver l'état fondamental du modèle planaire d'Ising avec 0 champ magnétique est en P, avec un champ magnétique non nul, il est NP-difficile. La fonction de partition du modèle d'Ising plan avec 0 champ magnétique est en P, avec un champ magnétique non nul, il est NP-dur.

Voici un problème intéressant, avec un saut de complexité intéressant, comme la bande passante minimale que vous avez abordée dans votre question.

Laissez un graphe et T un Spanning Tree de G . La déviation pour un bord u v ∈ E ( G ) est l'unique , u - v chemin dans T . La congestion des e ∈ E ( T ) , désigné par c n g G , T ( e ) est le nombre de déviations qui contiennent e . La congestion de G dans T , notée c n g$G$$T$$G$$uv\in E(G)$$u$$v$$T$$e \in E(T)$$\mathrm{cng}_{G,T}(e)$$e$$G$$T$ , est la congestion maximale sur tousbords en T . La congestion arbre couvrant de G , notée s t c ( G ) , est l'encombrement minimum sur tousarbres couvrant de G . Le problème d'encombrement du spanning-tree demande si un graphe donné présente une congestion au maximum par k .$\mathrm{cng}_G(T)$$T$$G$$\mathrm{stc}(G)$$G$$k$

Le saut de complexité suivant est présenté dans: Bodlaender et al., Complexité paramétrée du problème d'encombrement du Spanning Tree , Algorithmica 64 (2012) 85-111 :

Pour chaque et d fixes , le problème peut être résolu en temps linéaire pour des graphes de degré au plus d . En revanche, si nous n'autorisons qu'un sommet de degré non borné, le problème devient immédiatement N P- complet pour tout k ≥ 8 fixé .$k$$d$$d$$\mathsf{NP}$$k\ge 8$

Je me demande pourquoi personne ne l'a mentionné:

Horn-Sat vs K-Sat

Je suppose que tout le monde sait ce que c'est. Si non:

Horn-Sat doit rechercher si un ensemble de clauses de horn est satisfaisable (chaque clause a au plus 1 littéral positif).

K-Sat doit rechercher si un ensemble de clauses est satisfaisable (chaque clause peut avoir plus de 1 littéraux positifs).

Donc, autoriser plus d'un littéral positif dans chaque clause rend le problème de P-complete NP-complet.

Coloration graphique

Comme mentionné dans une autre réponse, le 2-COL peut être résolu en temps polynomial tandis que le 3-COL est le NP-complet. Mais quand on augmente le nombre de couleurs, après quelques points (inconnus?), Le problème devient plus facile!

Par exemple, si nous avons N sommets et N couleurs, le problème peut être résolu en attribuant une couleur différente à chaque sommet.

In a similar vein: Permanent vs Determinant.

I just read a paper that deals with hypergraph partitioning. The Problem is defined as this, quote:

Given two parameters $k$ and $l$, $1 \leq l < k$, the problem [$P^l_k$] is defined as follows: Let $\mathcal{H} = (V, \mathcal{E})$ be a hypergraph and $t_1, \dots, t_k$ be non-negative integers such that $|V| = n = \sum^k_{i=1} t_i$ and $|\mathcal{E}| = m$. Does there exist a colouring (partition) of $V$ in $k$ subsets of size $t_1, \dots, t_k$ such that the vertices of each hyperedge in $\mathcal{E}$ are coloured with at most $l$ colours?

In general, it is proven that:

• $P^1_k$ is solvable in polynomial time (in $n,m$) for fixed $k \geq 2$
• $P^l_k$ is NP-complete for all fixed $2 \leq l < k$

If this is not "jump" enough, read on. For hypergraphs with disjoint hyperedges, it is shown:

• $P^1_k$ is NP-complete for all fixed $k \geq 2$
• $P^l_k$ is solvable in linear time (in $m$) for fixed $2 \leq l < k$

Laurent Lyaudet. 2010. NP-hard and linear variants of hypergraph partitioning. Theor. Comput. Sci. 411, 1 (January 2010), 10-21. http://dx.doi.org/10.1016/j.tcs.2009.08.035

Interesting complexity jumps are known for the job shop scheduling problem.

In the job shop problem we have a set of $n$ jobs that must be processed on a given set $M$ of $m$ machines. Each job $j$ consists of a chain of $\mu_j$ operations $O_{1j},O_{2j},\dots,O_{\mu_jj}$. Operation $O_{ij}$ must be processed during $p_{ij}$ time units without interruption on machine $m_{ij}\in M$. A feasible schedule is one in which operation is scheduled only after all its preceding operations have been completed, and each machine processes at most one operation at a time. For any given schedule, let $C_j$ be the completioon time of the last operation of job $j$. Taken here.

There are such objectives as minimizing the makespan $C_{max}=max_jC_j$ and total completion time $\sum C_j$. Regular criteria are defined here.

In the notation of Graham et al. this problem is denoted as $J||\gamma$, where $\gamma$ denotes the objective function to be minimized.

$J2|n=k|F$ and $J|n=2|F$ are polynomially solvable. Here $J2$ $(n=k)$ means that the number of machines (jobs) is fixed and equals $2$ $(k)$. $F$ means an arbitrary regular criterion.

$J3|n=3|C_{max}$, $J3|n=3|\sum C$ are weakly NP-hard.

$J2||C_{max}$, $J2||\sum C$ are strongly NP-hard.

Thus, here we can see that there is a jump when we go from two jobs/machines to three.

In many cases, approximating NP-optimization problems give rise to sharp complexity jumps. For example, SET COVER can be approximated within a factor of $\ln n$ in polynomial time (by the Greedy Algorithm), but it is NP-hard to approximate within a factor of $(1-o(1))\ln n$.

Je pense que le triangle pascal le serait. Chaque ligne du triangle pascal est la somme de$2^n$. Les éléments sont des coefficients binomiaux. Donc, si vous trouvez un problème dont les performances peuvent être décrites à l'aide de coefficients binomiaux, alors la résolution de tous ces problèmes associés à la n-rangée du triangle pascal prend déjà$2^n$. Mais notez que$(a+b)^n=\sum_{i\in{0..n}}{{n}\choose{i}}a^ib^{n-i}$peut être représenté comme un polynôme (de 'a') qui a comme facteur binomial fois les puissances de 'b'. Si 'b' est constant, il s'agit d'un polynôme d'ordre n$p_b(a)$. Réglage$a=b=1$ vous obtenez l'expansion de $2^n=p_1(1)$comme une somme. Supposons maintenant que vous avez une matrice de problèmes de performance en deux variables proportionnelles aux coefficients binomiaux (comparés à la taille du problème décrite par deux variables) disposées comme un triangle pascal. Il faut ensuite résoudre tous les problèmes au n$DTIME(2^n)$. Les coefficients binomiaux décrivent le nombre de façons différentes de choisir les k-combinaisons à partir de n éléments. Donc, si votre algorithme dépend de l'énumération de k-combinaisons de n éléments $(k<n)$l'algorithme ne peut pas être un temps polynomial. Parce que si ce problème était du temps polynomial, alors l'argument ci-dessus prouve$P=NP=DTIME(2^n)$, puisque la somme de deux polynômes est un polynôme. Mais corrigez les preuves de$P=NP$ problème de toute façon sont rares.