Parece que muchas personas creen que , en parte porque creen que la factorización no es solucionable por tiempo múltiple. (Shiva Kintali ha enumerado algunos otros problemas candidatos aquí ).
Por otro lado, Grötschel, Lovász y Schrijver han escrito que "muchas personas creen que ". Esta cita se puede encontrar en Algoritmos geométricos y optimización combinatoria, y Schrijver hace afirmaciones similares en Optimización combinatoria: poliedros y eficiencia . Esta imagen deja en claro dónde se encuentra Jack Edmonds sobre el tema.
¿Qué evidencia respalda la creencia en ? ¿O para apoyar P = N P ∩ c o N P ?
cc.complexity-theory
np
conditional-results
Austin Buchanan
fuente
fuente
Respuestas:
Teorema 3.1 de permutaciones unidireccionales y lenguajes de autocontrol C. Homan y M. Thakur, Journal of Computer and System Sciences, 67 (3): 608-622, noviembre de 2003. [ como .pdf ] establece que si y solo si ("el peor de los casos") existen permutaciones unidireccionales. Teorema 3.2 recuerda 10 hipótesis adicionales que se han demostrado para ser equivalente a P ≠ U P ∩ c o U P .P≠UP∩coUP P≠UP∩coUP
Además, tenemos fuertes razones para conjeturar que . Por lo tanto, lo anterior teorema y el resultado conjetura en una razón de peso para creer que P ≠ N P ∩ C O N P .UP≠NP P≠NP∩coNP
Descargo de responsabilidad: moví la edición de Mohammad Al-Turkistany de mi respuesta a esta respuesta wiki comunitaria. Él cree que responde perfectamente a la pregunta ya que la existencia de permutaciones unidireccionales se cree ampliamente. Yo mismo aún no he entendido suficientemente la diferencia entre las funciones unidireccionales de "peor caso" y "caso promedio" para afirmar que realmente responde la pregunta.
fuente
Creo que existen generadores de números aleatorios de alta calidad muy eficientes en cuanto al espacio. A pesar de esta creencia, normalmente uso Mersenne Twister en mi código, que es de alta calidad, pero no es muy eficiente en cuanto al espacio. Falta un vínculo entre la eficiencia del espacio y NP∩coNP, es solo una sensación de que hay un vínculo.
Permítanme tratar de dar una razón por la que creo que la "aleatoriedad verdadera" puede simularse / aproximarse de manera muy eficiente. Sabemos que es posible producir números pseudoaleatorios que sean suficientemente aleatorios para todos los fines prácticos (incluida la criptografía). También sabemos que usar (una pequeña cantidad de números fijos) números primos grandes en la construcción de generadores de números pseudoaleatorios rara vez es una mala idea. Sabemos por conjeturas como la de Riemann que casi todos los números primos contienen un alto grado de aleatoriedad, pero también sabemos que aún no podemos probar esto rigurosamente.
¿Existe una explicación intuitiva de por qué los números primos se comportan como números aleatorios? Los números primos son el complemento de los números compuestos. El complemento de un conjunto con buen comportamiento suele ser más complicado que el conjunto original. Los números compuestos están compuestos de números primos, lo que a su vez ya le da a este conjunto una cierta complejidad.
Antecedentes Una vez intenté entender por qué P ≠ NP es difícil. Me preguntaba si aproximar los grupos de simetría interna de una instancia problemática por grupos nilpotentes podría no conducir a un "algoritmo de abstracción" capaz de ver la estructura interna de la instancia problemática. Pero luego me di cuenta de que incluso calcular la estructura de un grupo nilpotente contiene factorización como un caso especial. La cuestión de los subgrupos simples de un grupo cíclico de orden n es equivalente a determinar los factores primos de n. Y la clasificación de grupos finitos nilpotentescontiene subproblemas aún peores relacionados con el isomorfismo gráfico. Eso fue suficiente para convencerme de que este enfoque no ayudará. Pero mi siguiente paso fue tratar de entender por qué es difícil factorizar, y la respuesta anterior es lo que se me ocurrió. Fue suficiente para convencerme, así que tal vez también sea convincente para otras personas. (En aquel entonces, no conocía los grupoides o los semigrupos inversos, que probablemente sean más adecuados que los grupos nilpotentes para manejar simetrías internas. Aún así, el argumento de por qué este enfoque no será eficiente sigue siendo el mismo).
fuente