Lista de problemas NP-completos
De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

Ésta es una lista dinámica y es posible que nunca pueda satisfacer estándares particulares de completitud. Puede ayudar agregando elementos faltantes con fuentes confiables .

Esta es una lista de algunos de los problemas más comúnmente conocidos que son NP-completos cuando se expresan como problemas de decisión . Como se conocen cientos de estos problemas, esta lista no es de ninguna manera exhaustiva. Muchos problemas de este tipo se pueden encontrar en Garey y Johnson (1979) .

Gráficos e hipergráficos

Los gráficos ocurren con frecuencia en las aplicaciones diarias. Los ejemplos incluyen redes biológicas o sociales, que contienen cientos, miles e incluso miles de millones de nodos en algunos casos (por ejemplo, Facebook o LinkedIn ).

Los casos especiales NP-completos incluyen el problema del conjunto dominante de bordes , es decir, el problema del conjunto dominante en los gráficos lineales. Las variantes NP-completas incluyen el problema del conjunto dominante conectado y el problema del árbol de expansión máxima de hojas . [11]
  • Problema de ancho de banda [12]
  • Problema de tapadera de camarilla [2] [13]
  • Coloración de rango también conocido como rango de ciclo
  • Árbol de expansión con restricción de grados [14]
  • Problema de cobertura exacto . Permanece NP-completo para 3 juegos. Resoluble en tiempo polinomial para 2 conjuntos (esto es una coincidencia ). [2] [15]
  • Conjunto de vértices de comentarios [2] [16]
  • Conjunto de arco de retroalimentación [2] [17]
  • Problema de homomorfismo gráfico [18]
  • Coloración de gráficos [2] [19]
  • Partición gráfico en subgrafos de tipos específicos (triángulos, isomórficas subgrafos , hamiltonianas subgrafos, bosques , matchings perfectos ) son conocidos NP-completo. La división en grupos es el mismo problema que colorear el complemento del gráfico dado. Un problema relacionado es encontrar una partición que sea óptima en términos del número de aristas entre las partes. [20]
  • Finalización hamiltoniana [21]
  • Problema del camino hamiltoniano , dirigido y no dirigido. [2] [22]
  • Problema de la ruta más larga [23]
  • Máximo subgrafo bipartito o (especialmente con bordes ponderados) corte máximo . [2] [24]
  • Conjunto independiente máximo [25]
  • Trayectoria inducida máxima [26]
  • Número de intersección del gráfico [27]
  • Dimensión métrica de un gráfico [28]
  • K-corte mínimo
  • Árbol de Steiner o árbol de expansión mínimo para un subconjunto de los vértices de un gráfico. [2] (El árbol de expansión mínimo para un gráfico completo se puede resolver en tiempo polinomial).
  • Maximización de la modularidad [29]
  • Ancho de ruta [30]
  • Cobertura del conjunto (también llamado problema de cobertura mínima ) Esto es equivalente, al trasponer la matriz de incidencia, al problema del conjunto de golpes. [2] [31]
  • Establecer problema de división [32]
  • Árbol de expansión de longitud de trayecto total más corto [33]
  • Prueba de pendiente número dos [34]
  • Ancho de árbol [30]
  • Cubierta de vértice [2] [35]

Programación matemática

  • Problema de 3 particiones [36]
  • Problema de embalaje del contenedor [37]
  • Problema de la mochila , problema de la mochila cuadrática , y varias variantes [2] [38]
  • Variaciones sobre el problema del viajante . El problema de las gráficas es NP-completo si se supone que las longitudes de los bordes son enteros. El problema para los puntos en el plano es NP-completo con la métrica euclidiana discretizada y la métrica rectilínea. Se sabe que el problema es NP-difícil con la métrica euclidiana (no discretizada). [39]
  • Vendedor ambulante de cuello de botella [40]
  • Programación de enteros . La variante donde se requiere que las variables sean 0 o 1, llamada programación lineal cero-uno, y varias otras variantes también son NP-completas [2] [41]
  • Cuadrados latinos (el problema de determinar si un cuadrado parcialmente lleno se puede completar para formar uno)
  • Coincidencia numérica tridimensional [42]
  • Problema de partición [2] [43]
  • Problema de asignación cuadrática [44]
  • Resolver polinomios cuadráticos de dos variables sobre números enteros. [45] Dados los números enteros positivos , encuentre números enteros positivos tales que
  • Programación cuadrática (NP-duro en algunos casos, P si es convexo)
  • Problema de suma de subconjuntos [46]

Lenguajes formales y procesamiento de cadenas

  • Cadena más cercana [47]
  • Problema de subsecuencia común más largo en múltiples secuencias [48]
  • La variante acotada del problema de correspondencia postal [49]
  • Supersecuencia común más corta [50]
  • Problema de corrección de cuerda a cuerda [51]

Juegos y rompecabezas

  • Bolsa (Corral) [52]
  • Acorazado
  • Bulls and Cows , comercializado como Master Mind : ciertos problemas de optimización pero no el juego en sí.
  • Eternidad II
  • ( Generalizado ) FreeCell [53]
  • Fillomino [54]
  • Hashiwokakero [55]
  • Heyawake [56]
  • ( Generalizado ) Locura instantánea [57]
  • Kakuro (Sumas cruzadas) [58]
  • Kingdomino [59]
  • Kuromasu (también conocido como Kurodoko) [60]
  • LaserTank [61]
  • Lemmings (con un límite de tiempo polinomial) [62]
  • Iluminar [63]
  • Masyu [64]
  • Problema de coherencia del buscaminas [65] (pero véase Scott, Stege y van Rooij [66] )
  • Nimber (o número de Grundy) de un gráfico dirigido. [67]
  • Numberlink
  • Nonogramas
  • Nurikabe [68]
  • Pandemia ( generalizada ) [69]
  • Solución óptima para el cubo de Rubik N × N × N [70]
  • Mismo juego
  • ( Generalizado ) Conjunto [71]
  • Enlace deslizante en una variedad de cuadrículas [72] [73] [74]
  • Sudoku ( generalizado ) [72] [75]
  • Problemas relacionados con el Tetris [76]
  • Aritmética verbal

Otro

  • Problema de asignación de literas [77]
  • Intermediación
  • Montaje de un bloque Bitcoin óptimo . [78]
  • Problema de satisfacibilidad booleano (SAT). [2] [79] Hay muchas variaciones que también son NP-completas. Una variante importante es donde cada cláusula tiene exactamente tres literales (3SAT), ya que se usa en la prueba de muchos otros resultados de NP-completitud. [80]
  • Consulta booleana conjuntiva [81]
  • Orden cíclico
  • Problema de satisfacibilidad del circuito
  • Problema de ubicación de instalaciones no capacitadas
  • Problema de programación de Flow Shop
  • Problema de asignación generalizado
  • Prueba de planaridad ascendente [34]
  • Encontrar la solución mínimo global de un método de Hartree-Fock problema [82]
  • Problema de los hospitales y los residentes con las parejas
  • Algunos problemas relacionados con la programación del taller
  • Triángulo monocromático [83]
  • Conjunto mínimo máximo independiente también conocido como conjunto mínimo independiente dominante [84]
Los casos especiales NP-completos incluyen el problema de emparejamiento mínimo máximo , [85] que es esencialmente igual al problema de conjunto que domina el borde (ver arriba).
  • Problema de isomorfismo de subgrafo común máximo [86]
  • Árbol de expansión de grado mínimo
  • Árbol de k-spanning mínimo
  • Centro k métrico
  • Máxima 2-Satisfabilidad [87]
  • Lógica modal S5-Satisfacción
  • Algunos problemas relacionados con la programación del multiprocesador
  • Máximo volumen submatriz - problema de seleccionar el mejor subconjunto condicionado de una más grande de la matriz. Esta clase de problema está asociada con las factorizaciones QR que revelan el rango y el diseño experimental óptimo D. [88]
  • Cadenas de suma mínima para secuencias. [89] Se desconoce la complejidad de las cadenas de suma mínima para números individuales. [90]
  • Polinomios univariados no lineales sobre GF [2 n ], n la longitud de la entrada. De hecho, sobre cualquier GF [q n ].
  • Programación de tienda abierta
  • Ancho de ruta , [30] o, de manera equivalente, espesor del intervalo y número de separación de vértices [91]
  • Problema de distancia de clasificación de panqueques para cuerdas [92]
  • cartero k-chino
  • Problema de isomorfismo de subgrafo [93]
  • Variaciones del problema del árbol de Steiner . Específicamente, con la métrica euclidiana discretizada, métrica rectilínea. Se sabe que el problema es NP-difícil con la métrica euclidiana (no discretizada). [94]
  • Establecer embalaje [2] [95]
  • Posibilidad de serializar los historiales de las bases de datos [96]
  • Programación para minimizar el tiempo de finalización ponderado
  • Aproximación escasa
  • Clasificación de bloques [97] (Clasificación por movimientos de bloque)
  • Creación de instancias de segundo orden
  • Ancho de árbol [30]
  • Prueba de si un árbol puede representarse como árbol de expansión mínimo euclidiano
  • Modelo de Ising tridimensional [98]
  • Problema de ruta del vehículo

Ver también

  • Teoría existencial de los reales # Problemas completos
  • Los 21 problemas NP-completos de Karp
  • Lista de problemas completos de PSPACE
  • Reducción (complejidad)

Notas

  1. ^ Grigoriev y Bodlaender (2007) .
  2. ^ a b c d e f g h i j k l m n o p q Karp (1972)
  3. ^ Garey y Johnson (1979) : SP1
  4. ^ Garey y Johnson (1979) : GT18
  5. ^ Garey y Johnson (1979) : ND5
  6. ^ Garey y Johnson (1979) : ND25, ND27
  7. ^ Garey y Johnson (1979) : GT19
  8. ^ Garey y Johnson (1979) : GT5
  9. ^ Garey y Johnson (1979) : GT3
  10. ^ Garey y Johnson (1979) : GT2
  11. ^ Garey y Johnson (1979) : ND2
  12. ^ Garey y Johnson (1979) : GT40
  13. ^ Garey y Johnson (1979) : GT17
  14. ^ Garey y Johnson (1979) : ND1
  15. ^ Garey y Johnson (1979) : SP2
  16. ^ Garey y Johnson (1979) : GT7
  17. ^ Garey y Johnson (1979) : GT8
  18. ^ Garey y Johnson (1979) : GT52
  19. ^ Garey y Johnson (1979) : GT4
  20. ^ Garey y Johnson (1979) : GT11, GT12, GT13, GT14, GT15, GT16, ND14
  21. ^ Garey y Johnson (1979) : GT34
  22. ^ Garey y Johnson (1979) : GT37, GT38, GT39
  23. ^ Garey y Johnson (1979) : ND29
  24. ^ Garey y Johnson (1979) : GT25, ND16
  25. ^ Garey y Johnson (1979) : GT20
  26. ^ Garey y Johnson (1979) : GT23
  27. ^ Garey y Johnson (1979) : GT59
  28. ^ Garey y Johnson (1979) : GT61
  29. ^ Brandes, Ulrik ; Delling, Daniel; Gaertler, Marco; Görke, Robert; Hoefer, Martin; Nikoloski, Zoran; Wagner, Dorothea (2006), Maximizar la modularidad es difícil , arXiv : physics / 0608255 , Bibcode : 2006physics ... 8255B
  30. ↑ a b c d Arnborg, Corneil y Proskurowski (1987)
  31. ^ Garey y Johnson (1979) : SP5, SP8
  32. ^ Garey y Johnson (1979) : SP4
  33. ^ Garey y Johnson (1979) : ND3
  34. ^ a b Garg, Ashim; Tamassia, Roberto (1995). "Sobre la complejidad computacional de las pruebas de planaridad ascendente y rectilínea". Apuntes de conferencias en Ciencias de la Computación . 894/1995. págs. 286-297. doi : 10.1007 / 3-540-58950-3_384 . ISBN 978-3-540-58950-1.
  35. ^ Garey y Johnson (1979) : GT1
  36. ^ Garey y Johnson (1979) : SP15
  37. ^ Garey y Johnson (1979) : SR1
  38. ^ Garey y Johnson (1979) : MP9
  39. ^ Garey y Johnson (1979) : ND22, ND23
  40. ^ Garey y Johnson (1979) : ND24
  41. ^ Garey y Johnson (1979) : MP1
  42. ^ Garey y Johnson (1979) : SP16
  43. ^ Garey y Johnson (1979) : SP12
  44. ^ Garey y Johnson (1979) : ND43
  45. ^ Problemas de decisión NP-completos para polinomios cuadráticos
  46. ^ Garey y Johnson (1979) : SP13
  47. ^ Lanctot, J. Kevin; Li, Ming; Ma, Bin; Wang, Shaojiu; Zhang, Louxin (2003), "Distinguiendo problemas de selección de cuerdas", Information and Computation , 185 (1): 41-55, doi : 10.1016 / S0890-5401 (03) 00057-9 , MR 1994748 
  48. ^ Garey y Johnson (1979) : SR10
  49. ^ Garey y Johnson (1979) : SR11
  50. ^ Garey y Johnson (1979) : SR8
  51. ^ Garey y Johnson (1979) : SR20
  52. ^ Friedman, Erich. "Los rompecabezas de Corral son NP-completos" (PDF) . Consultado el 17 de agosto de 2021 .
  53. ^ Malte Helmert, Resultados de complejidad para dominios de referencia estándar en planificación, Inteligencia artificial 143 (2): 219-262, 2003.
  54. ^ Yato, Takauki (2003). Complejidad e integridad de encontrar otra solución y su aplicación a los rompecabezas . CiteSeerX 10.1.1.103.8380 . 
  55. ^ "HASHIWOKAKERO es NP-Complete" .
  56. ^ Holzer y Ruepp (2007)
  57. ^ Garey y Johnson (1979) : GP15
  58. ^ Takahiro, Seta (5 de febrero de 2002). "Las complejidades de los rompecabezas, suma cruzada y sus problemas de otra solución (ASP)" (PDF) . Consultado el 18 de noviembre de 2018 .
  59. ^ Nguyen, Viet-Ha; Perrot, Kévin; Vallet, Mathieu (24 de junio de 2020). "NP-completitud del juego KingdominoTM" . Informática Teórica . 822 : 23–35. doi : 10.1016 / j.tcs.2020.04.007 . ISSN 0304-3975 . 
  60. ^ Kölker, Jonas (2012). "Kurodoko es NP-completo" (PDF) . Revista de procesamiento de información . 20 (3): 694–706. doi : 10.2197 / ipsjjip.20.694 . S2CID 46486962 . Archivado desde el original (PDF) el 12 de febrero de 2020.  
  61. ^ Alexandersson, Per; Restadh, Petter (2020). "LaserTank es NP-Complete". Aspectos matemáticos de las ciencias informáticas y de la información . Apuntes de conferencias en Ciencias de la Computación. Springer International Publishing. 11989 : 333–338. arXiv : 1908.05966 . doi : 10.1007 / 978-3-030-43120-4_26 . ISBN 978-3-030-43119-8. S2CID  201058355 .
  62. ^ Cormode, Graham (2004). La dureza del juego de los lemmings, u Oh no, más pruebas de NP-completitud (PDF) .
  63. ^ Light Up es NP-Complete
  64. ^ Friedman, Erich (27 de marzo de 2012). "Los rompecabezas de perlas son NP-completos" . Archivado desde el original el 4 de febrero de 2012.
  65. ↑ Kaye (2000)
  66. ↑ Allan Scott, Ulrike Stege, Iris van Rooij, Minesweeper puede no ser NP-completo, pero no obstante es difícil, The Mathematical Intelligencer 33 : 4 (2011), págs. 5-17.
  67. ^ Garey y Johnson (1979) : GT56
  68. ^ Holzer, Markus; Klein, Andreas; Kutrib, Martin (2004). "Sobre la NP-integridad del rompecabezas de lápiz NURIKABE y sus variantes" (PDF) . Actas de la 3ª Conferencia Internacional sobre Diversión con Algoritmos . S2CID 16082806 . Archivado desde el original (PDF) el 11 de febrero de 2020.   Enlace externo en |journal=( ayuda )
  69. ^ Nakai, Kenichiro; Takenaga, Yasuhiko (2012). "NP-Completitud de la pandemia" . Revista de procesamiento de información . 20 (3): 723–726. doi : 10.2197 / ipsjjip.20.723 . ISSN 1882-6652 . 
  70. ^ Demaine, Erik; Eisenstat, Sarah; Rudoy, ​​Mikhail (2018). Resolver el cubo de Rubik de manera óptima es NP-completo . 35o Simposio sobre Aspectos Teóricos de la Informática (STACS 2018). doi : 10.4230 / LIPIcs.STACS.2018.24 .
  71. ^ http://pbg.cs.illinois.edu/papers/set.pdf
  72. ^ a b Sato, Takayuki; Seta, Takahiro (1987). Complejidad e integridad de encontrar otra solución y su aplicación a los rompecabezas (PDF) . Simposio Internacional de Algoritmos (SIGAL 1987).
  73. ^ Nukui; Uejima (marzo de 2007). "Completitud ASP del rompecabezas Slither Link en varias cuadrículas" . Notas Ipsj Sig . 2007 (23): 129-136.
  74. ^ Kölker, Jonas (2012). "Las variantes de enlace deslizante seleccionadas son NP-completas" . Revista de procesamiento de información . 20 (3): 709–712. doi : 10.2197 / ipsjjip.20.709 .
  75. ^ UNA ENCUESTA DE ROMPECABEZAS NP-COMPLETO, Sección 23; Graham Kendall, Andrew Parkes, Kristian Spoerer; Marzo de 2008. (icga2008.pdf)
  76. ^ Demaine, Eric D .; Hohenberger, Susan; Liben-Nowell, David (25 a 28 de julio de 2003). Tetris es difícil, incluso aproximado (PDF) . Actas de la 9ª Conferencia Internacional de Computación y Combinatoria (COCOON 2003) . Big Sky, Montana.
  77. ^ Lim, Andrew (1998), "El problema de planificación del atraque", Cartas de investigación de operaciones , 22 (2-3): 105-110, doi : 10.1016 / S0167-6377 (98) 00010-8 , MR 1653377 
  78. ^ J. Bonneau, "La minería de Bitcoin es NP-hard
  79. ^ Garey y Johnson (1979) : LO1
  80. ^ Garey y Johnson (1979) : p. 48
  81. ^ Garey y Johnson (1979) : SR31
  82. ^ Complejidad computacional en estructura electrónica
  83. ^ Garey y Johnson (1979) : GT6
  84. ^ Conjunto dominante independiente mínimo
  85. ^ Garey y Johnson (1979) : GT10
  86. ^ Garey y Johnson (1979) : GT49
  87. ^ Garey y Johnson (1979) : LO5
  88. ^ https://web.archive.org/web/20150203193923/http://www.meliksah.edu.tr/acivril/max-vol-original.pdf
  89. ^ Peter Downey, Benton Leong y Ravi Sethi. "Computación de secuencias con cadenas de adición" SIAM J. Comput., 10 (3), 638–646, 1981
  90. ^ DJ Bernstein, "Algoritmo de potenciación de Pippinger (borrador)
  91. ^ Kashiwabara y Fujisawa (1979) ; Ohtsuki y col. (1979) ; Lengauer (1981) .
  92. ^ Hurkens, C .; Iersel, LV; Keijsper, J .; Kelk, S .; Stougie, L .; Tromp, J. (2007). "Inversiones de prefijo en cadenas binarias y ternarias". SIAM J. Matemáticas discretas . 21 (3): 592–611. arXiv : matemáticas / 0602456 . doi : 10.1137 / 060664252 .
  93. ^ Garey y Johnson (1979) : GT48
  94. ^ Garey y Johnson (1979) : ND13
  95. ^ Garey y Johnson (1979) : SP3
  96. ^ Garey y Johnson (1979) : SR33
  97. ^ Bein, WW; Larmore, LL; Latifi, S .; Sudborough, IH (1 de enero de 2002). La clasificación por bloques es difícil . Simposio Internacional de Arquitecturas, Algoritmos y Redes Paralelos, 2002. I-SPAN '02. Actas . págs. 307–312. doi : 10.1109 / ISPAN.2002.1004305 . ISBN 978-0-7695-1579-3. S2CID  32222403 .
  98. ^ Barry Arthur Cipra , "El modelo Ising es NP-Complete", SIAM News, Vol 33, No 6.

Referencias

General

  • Garey, Michael R .; Johnson, David S. (1979), Computadoras e intratabilidad: una guía para la teoría de NP-Completeness , W. H. Freeman , ISBN 0-7167-1045-5. Este libro es un clásico, desarrolla la teoría y luego cataloga muchos problemas NP-Complete.
  • Cook, SA (1971). "La complejidad de los procedimientos de demostración de teoremas". Actas, Tercer Simposio Anual de ACM sobre Teoría de la Computación, ACM, Nueva York . págs. 151-158. doi : 10.1145 / 800157.805047 .
  • Karp, Richard M. (1972). "Reducibilidad entre problemas combinatorios". En Miller, Raymond E .; Thatcher, James W. (eds.). Complejidad de los cálculos informáticos . Asamblea plenaria. págs. 85-103.
  • Dunne, PE "Una lista comentada de problemas NP-completos seleccionados" . COMP202, Departamento de Ciencias de la Computación, Universidad de Liverpool . Consultado el 21 de junio de 2008 .
  • Crescenzi, P .; Kann, V .; Halldórsson, M .; Karpinski, M .; Woeginger, G . "Un compendio de problemas de optimización de NP" . KTH NADA, Estocolmo . Consultado el 21 de junio de 2008 .
  • Dahlke, K. "Problemas NP-completos" . Proyecto de referencia matemática . Consultado el 21 de junio de 2008 .

Problemas específicos

  • Friedman, E (2002). "Los rompecabezas de perlas son NP-completos" . Universidad Stetson, DeLand, Florida . Consultado el 21 de junio de 2008 .
  • Grigoriev, A; Bodlaender, HL (2007). "Algoritmos para gráficos incrustables con pocos cruces por borde". Algoritmica . 49 (1): 1–11. CiteSeerX  10.1.1.61.3576 . doi : 10.1007 / s00453-007-0010-x . Señor  2344391 . S2CID  8174422 .
  • Hartung, S; Nichterlein, A (2012). Cómo se calcula el mundo . Apuntes de conferencias en Ciencias de la Computación. 7318 . Springer, Berlín, Heidelberg. págs. 283-292. CiteSeerX  10.1.1.377.2077 . doi : 10.1007 / 978-3-642-30870-3_29 . ISBN 978-3-642-30869-7. S2CID  6112925 .
  • Holzer, Markus; Ruepp, Oliver (2007). "Los problemas del diseño de interiores: un análisis de la complejidad del juego Heyawake" (PDF) . Actas, 4ta Conferencia Internacional sobre Diversión con Algoritmos, LNCS 4475 . Springer, Berlín / Heidelberg. págs. 198–212. doi : 10.1007 / 978-3-540-72914-3_18 . ISBN 978-3-540-72913-6.
  • Kaye, Richard (2000). "Buscaminas es NP-completo". Intelligencer matemático . 22 (2): 9-15. doi : 10.1007 / BF03025367 . S2CID  122435790 .Más información disponible en línea en las páginas del Buscaminas de Richard Kaye .
  • Kashiwabara, T .; Fujisawa, T. (1979). "NP-completitud del problema de encontrar un gráfico de intervalo de número mínimo de clique que contenga un gráfico dado como un subgráfico". Actas . Simposio Internacional de Circuitos y Sistemas . págs. 657–660.
  • Ohtsuki, Tatsuo; Mori, Hajimu; Kuh, Ernest S .; Kashiwabara, Toshinobu; Fujisawa, Toshio (1979). "Gráficos de intervalo y asignación de puerta lógica unidimensional". Transacciones IEEE en circuitos y sistemas . 26 (9): 675–684. doi : 10.1109 / TCS.1979.1084695 .
  • Lengauer, Thomas (1981). "Guijarros blanco y negro y separación de gráficos". Acta Informatica . 16 (4): 465–475. doi : 10.1007 / BF00264496 . S2CID  19415148 .
  • Arnborg, Stefan; Corneil, Derek G .; Proskurowski, Andrzej (1987). "Complejidad de encontrar incrustaciones en un árbol k ". Revista SIAM de Métodos Algebraicos y Discretos . 8 (2): 277–284. doi : 10.1137 / 0608024 .
  • Cormode, Graham (2004). "La dureza del juego de los lemmings, u Oh no, más pruebas de NP-completitud". Actas de la Tercera Conferencia Internacional sobre Diversión con Algoritmos (FUN 2004) . págs. 65–76.

enlaces externos

  • Un compendio de problemas de optimización de NP
  • Gráfica de problemas NP-completos
Obtenido de " https://en.wikipedia.org/w/index.php?title=List_of_NP-complete_problems&oldid=1039162253 "
Contribute a better translation