Anex:Problemes NP-complets
Esta és una llista d'alguns dels problemes més comunament coneguts que es NP-complet Quan s'expressa com problema de decisió. Com hi ha centenars d'estos problemes coneguts, esta llista no és de cap manera exhaustiva. Molts dels problemes d'este tipo es poden trobar en Garey y Johnson (1979).
- Esta és una llista incompleta, que mai pot ser capaç de satisfer les normes particulars per a l'integritat. Vosté pot ajudar ampliant-la en entrades que es poden adquirir de manera fiable.
Grafos i hypergrafos
[editar | editar còdic]Grafos es produïxen en freqüència en aplicacions d'us diari. Els eixemples inclouen les rets biològiques o socials, que contenen centenars, mills i inclús mils de millons de nodos en alguns casos (vore per eixemple Facebook o LinkedIn).
- 1-planaridadPlantilla:Sfnp
- Joc de 3 dimensions[1][2]
- Dimensió Bipartita[3]
- Arbres de cost mínim[4]
- Problema d'inspecció de ruta (també cridat 'problema del carter chinenc' ) para grafos mixts (tenint abdós arcs dirigits i no dirigits). El programa és resoluble en temps polinomial si el grafo té tots els arcs dirigits o tots no dirigit. Les variants inclouen el problema carter rural[5]
- Problema del Clique[1][6]
- Coloració completa, número cromàtic[7]
- Número de Domatic[8]
- Dominant set, també conegut com a número dominació[9]
- Casos especials NP-complets inclouen la desequilibrante brode set problema, és dir, el conjunt de problemes dominant en Grafos de llínees. Variants NP-complets inclouen la desequilibrante conectat ajustada problema i la [arbre] [màxim de full que comprén] problema[10]
- Problema ample de banda[11]
- Problema de cobertura de Clique[1][12]
- Ranc de coloració
- Grau en llimitacions(arbre abarcador)[13]
- Problema de Cobertura exacta. NP-complet per a 3 conjunts. Solubles en temps polinòmic per a 2 conjunts (est és un joc)[1]Garey y Johnson (1979):. SP2 </ref>
- Retroalimentación en conjunt de vèrtiços[1][14]
- Retroalimentación en conjunt d'arcs[1][15]
- Problema de Grafos homomorfos[16]
- Coloració de Grafos[1][17]
- Partició de Grafos en subgrafos de tipos específics (triànguls, isomorfo subgrafos, hamiltoniano subgrafos, boscs, joc perfecte s) es coneixen NP-complet. Partició en caçoles és el mateix problema que colorear de complementar del Grafo donat. Un problema relacionat és trobar una partició que és térmens òptims de la cantitat d'arcs entre les parts[18]
- Finalisació d'Hamilton[19]
- Problema del camí hamiltoniano, dirigida i no dirigida[1][20]
- Problema del camí màxim[21]
- Subgrafo màxim bipartito o (especialment en arcs ponderats) màxima cort[1][22]
- Conjunt independent màxim[23]
- Màxima ruta induïda[24]
- número d'intersecció del Grafo[25]
- Acotat mètric d'un Grafo[26]
- K-talle mínim
- arbre d'expansió mínim., O arbre de Steiner, per a un subconjunt dels vèrtiços d'un grafo[1] (L'arbre d'expansió mínima d'un Grafo de tot és solucionable en temps polinòmic).
- Problema del camí ample[27]
- Conjunt de coberta (també cridat 'cobertura mínima' problema) Açò és equivalent, per mig de la transposició de la matriu d'incidència, per al conjunt de problemes que colpeja[1] <. ref>[28]: SP5, SP8 </ref>
- Problema de divisió de conjunts[29]
- Llongitut del camí més curt en arbres abarcadores[30]
- Número pendent dos proves[31]
- Ample d'arbres[27]
- Coberta de vèrtiços[1][32]
La programació matemàtica
[editar | editar còdic]- Problema 3-partició[33]
- Problema d'Embalage[34]
- Problema de la mochila i vàries variants[1][35]
- Variacions sobre el problema del viajante. El problema per als Grafos és NP-complet si les llongituts dels arcs són sancers assumits. El problema per als punts en el pla és NP-complet en la mètrica i rectilínea euclidiana discretizado. El problema és conegut per ser NP-dur en el (discretizado no) euclidiana mètriques[36]
- Coll de botella del viajante[37]
- Programació sancera. La variant a on es requerixen les variables a ser 0 o 1, cridada programació llineal zero-un, i vàries atres variants també són NP-complet[1][38]
- Numérical joc de 3 dimensions[39]
- Problema de repartiment[1][40]
- Problema d'assignació quadràtica[41]
- Programació quadràtica (NP-difícil en alguns casos, si P convexo)
- Problema de la suma de subconjunts[42]
Els llenguages formals i processament de cadenes
[editar | editar còdic]- La variant acotada del problema de correspondència de mensages[44]
- Supersecuencia comú més curta[45]
- Problema de correcció cadena a cadena[46]
Jocs i rompecabezas
[editar | editar còdic]- Batalla Naval
- Adornat en joyes[47]
- Bous i Vaques, comercialisats com Ment Mestra
- Saga Candy Crush[48][47]
- Eternitat II
- (Generalisada) Carta blanca[49]
- Fillomino[50]
- Heyawake[51]
- (Generalisada) Locada immediata[52]
- Kakuro (sumes creuades)
- Kuromasu (també conegut com Kurodoko)[53]
- Lemmings[54]
- Encenga's[55]
- Masyu[56]
- Problema del Buscaminas[57] (pero vore Scott, Stege, i van Rooij[58])..
- Nimber (o número de Grundy) d'un grafo dirigit[59]
- Nonogramas
- Nurikabe
- SameGame
- Conexió deslizante en una varietat de rets[60][61][62][63]
- (Generalisada) Sudoku
- Super Mario Bros[64]
- Els problemes relacionats en Tetris
- Aritmètica verbal
Uns atres
[editar | editar còdic]- Problema de la galeria d'art i les seues variacions.
- Problema d'assignació d'amarre
- Montage d'un Bitcoin bloc òptima.[65]
- Problema satisfacció booleana (SAT)[1][66] Hi ha moltes variacions que també són NP complet. Una variant important és a on cada clàusula té exactament tres lliterals (3SAT), ya que s'utilisa en la prova de molts atres resultats NP-complets.[67]
- Consulta booleana en forma conjuntiva[68]
- Ordenament cíclico
- Problema de satisfacció de circuits
- Incapacitat sobre l'Ubicació
- Problema de planificació de circulació
- Problema d'assignació generalisada
- Prova de planaridad cap a dalt [31]
- Alguns dels problemes relacionats en la planificació
- Triàngul Monocromàtic[69]
- Conjunt independent mínim mínim conjunt dominant independent[70]
- Casos especials NP-complets inclouen el problema de mínim acoplament,[71] que és essencialment igual al problema del conjunt dominant d'arestes (vore més arriba).
- Problema del subgrafo isomorfo màxim[72]
- Grau mínim d'un arbre abarcador
- K-arbre abarcador mínim
- Mètriques k-centre
- Màxim 2-satisfacibilidad[73]
- Llògica modal S5-satisfacibilidad
- Alguns dels problemes relacionats en la programació multiprocessador
- Volum màxim d'una submatriz - problema de seleccionar el subconjunt d'una matriu mxn més gran millor acondicionat. Esta classe de problema s'associa en Ranc revelant factorización QR s i D de disseny experimental òptim.[74]
- Cadena d'adició mínimes per a les seqüències.[75] La complexitat de les cadenes d'adició mínims per a números individuals és desconegut[76]
- Polinomis no llineals invariantes sobre grafos [2 n </ sup>], n la llongitut de l'entrada. En efecte sobre qualsevol grafo [q n </ sup>].
- Planificació d'horaris en tendes
- Ample d'un camí,[77] o, equivalentemente, interval de gruixa i número de separació de vèrtiços[78]
- Classificació Pancake problema de la distància per a les cadenes[79]
- Problema del k-carter Chinenc
- Problema de subgrafos isomorfos[80]
- Les variacions del problema de l'arbre de Steiner. En concret, en la mètrica rectilínea euclidiana discretizada. El problema és conegut per ser NP-dur en la mètrica euclidiana no discretizada.[81]
- Establir embalage[1][82]
- Serialización de bases de senyes d'històries[83]
- Planificació per a minimisar el temps de finalisació ponderada
- Aproximació escassa
- Bloquejar Classificació (Classificació per moviments de blocs)
- Particularización de segon orde
- Ample d'arbre[77]
- Comprovar que un arbre pot representar-se com arbre abarcador de cost mínim euclidiano
- Model tridimensional Ising[84]
- Problema de ruteo de vehículs
<! - Problemes de llògica proposicional, en particular, els problemes de satisfacibilidad i les seues variants, són de particular interés pràctic perque molts problemes pràctics poden ser resolts per expressar-los com a problemes satisfacibilidad, i després utilisant eficients SAT solver s per a obtindre una exacta solució ràpida cita requerida .-->
Vore també
[editar | editar còdic]Notes
[editar | editar còdic]- ↑ 1,00 1,01 1,02 1,03 1,04 1,05 1,06 1,07 1,08 1,09 1,10 1,11 1,12 1,13 1,14 1,15 1,16 Karp ( 1972)
- ↑ : SP1
- ↑ : GT18
- ↑ : ND5
- ↑ :. ND25, ND27
- ↑ : GT19
- ↑ : GT5
- ↑ : GT3
- ↑ : GT2
- ↑ :. ND2
- ↑ : GT40
- ↑ : GT17
- ↑ : ND1
- ↑ : GT7
- ↑ : GT8
- ↑ : GT52
- ↑ : GT4
- ↑ :. GT11, GT12, GT13, GT14, GT15, GT16, ND14
- ↑ : GT34
- ↑ :. GT37, GT38, GT39
- ↑ : ND29
- ↑ :. GT25, ND16
- ↑ : GT20
- ↑ : GT23
- ↑ : GT59
- ↑ : GT61
- ↑ 27,0 27,1 Arnborg , Corneil y Proskurowski ( 1987)
- ↑ Garey y Johnson, 1979.
- ↑ : SP4
- ↑ : ND3
- ↑ 31,0 31,1 (1995) «En la complexitat computacional de proves planaridad cap a dalt i rectilínea», la conferència en Ciències de la Computació, pp. 286-297. doi:10.1007/3-540-58950-3_384.
- ↑ : GT1
- ↑ : SP15
- ↑ : SR1
- ↑ : MP9
- ↑ :. ND22, ND23
- ↑ : ND24
- ↑ Garey y Johnson ( 1979): MP1
- ↑ : SP16
- ↑ : SP12
- ↑ : ND43
- ↑ : SP13
- ↑ : SR10
- ↑ : SR11
- ↑ : SR8
- ↑ : SR20
- ↑ 47,0 47,1 L. Guala, S. Leucci, E. Natale. «Bejeweled, Crush Candy i atres partit i tres jocs són (NP) dur».
- ↑ Walsh, Toby. «caramelo Crush és NP-hard».
- ↑ Malte Helmert, resultats de complexitat per als dominis de referència estàndar en la planificació, l'Inteligència Artificial Diari 143 (2):. 219-262, 2003
- ↑ Tens que especificar títul = i url = al usar {{cita web}}..
- ↑ Holzer y Ruepp ( 2007)
- ↑ : GP15
- ↑ (2012).
- ↑ Erro en la cita: L'element
<ref>no és vàlit; puix no n'hi ha una referència en text nomenadaCormode04 - ↑ Light Up és NP-complet
- ↑ Friedman, Erich. «/pearl/pearl.html Perla Puzles són NP-complet».
- ↑ Kaye ( 2000)
- ↑ Allan Scott, Ulrike Stege, Iris van Rooij, Buscaminas no pot ser NP-complet, pero és difícil, no obstant, The Mathematical Intelligencer '33' : 4 (2011), pp 5-17
- ↑ :. GT56
- ↑
- ↑ «.ac.jp / yato / data2 / MasterThesis.pdf Complexitat i integritat de trobar una atra solució i la seua aplicació als rompecabezas».
- ↑
- ↑ (2012).
- ↑ G. Aloupis, ED Demaine, A. Guo. «/pdf/1203.1895v1.pdf clàssics jocs de Nintendo són (NP) Dur».
- ↑ J. Bonneau, "la mineria Bitcoin és NP -Hard
- ↑ :. LO1
- ↑ :. P. 48
- ↑ : SR31
- ↑ : GT6
- ↑ mínim Dominant Set Independent
- ↑ : GT10
- ↑ : GT49
- ↑ : OA5
- ↑ http://www.cs.rpi.edu/civria/max-vol-inapprox.pdf
- ↑ Peter Downey, Benton Leong, i Ravi Sethi. . "Informàtica Seqüències en Cadenes d'adició" SIAM J. Comput, 10 (3), 638-646, 1981
- ↑ [http:. //cr.yp .to / documents / pippenger.pdf DJ Bernstein, "algoritme de exponenciación de Pippinger (proyecte)]
- ↑ 77,0 77,1 Arnborg , Corneil y Proskurowski ( 1987)
- ↑ Kashiwabara y Fujisawa ( 1979);Ohtsuki et al. ( 1979);Lengauer ( 1981).
- ↑ Hurkens, C., Iersel, LV, Keijsper, J., Kelk, S., Stougie, L. i J. Tromp "reversiones de prefix en cadenes binarias i ternarias" . SIAM J. Matemàtica Discreta. 21 (3) (2007) 592-611.
- ↑ : GT48
- ↑ :. ND13
- ↑ : SP3
- ↑ : SR33
- ↑ Barry A. Cipra, "és el model de Ising NP-complet", SIAM News, Vol 33, No 6.
<ref> definida en las <references> con nombre «FOOTNOTEGareyJohnson1979{{{c}}}» no se utiliza en el texto anterior.Referències
[editar | editar còdic]- General
- (2009) Computers and intractability: a guide to the theory of NP-completeness, 27. print edició, New York [o.a]: Freeman. ISBN 978-0-7167-1045-5.. This book is a classic, developing the theory, then cataloguing many NP-Complete problems.
- Specific problems
- Further information available online at Richard Kaye's Minesweeper pages.
- .
- .
- .
- .
Enllaços externs
[editar | editar còdic]
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Anexo:Problemas NP-completos» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.