Esta es una especie de pregunta abierta, por lo que me disculpo de antemano.
¿Hay ejemplos de afirmaciones que (aparentemente) no tienen nada que ver con la complejidad o las máquinas de Turing, pero la respuesta implicaría ?
cc.complexity-theory
complexity-classes
p-vs-np
Dominic van der Zypen
fuente
fuente
Respuestas:
Un sistema de prueba para la lógica proposicional se denomina polinomialmente acotado , si cada tautologíaφ tiene una prueba en el sistema de polinomios de longitud en la longitud de φ .
La afirmación "No hay un sistema de prueba proposicional limitado polinómicamente" es equivalente a por un resultado clásico de Cook y Reckhow , por lo que implica .P ≠ N PNP≠co-NP P ≠ N P
fuente
La teoría de la complejidad geométrica (GCT) (también [1]) no se ha mencionado todavía. Es un gran programa ambicioso para conectar P vs NP a la geometría algebraica. Por ejemplo, una breve sinopsis de la encuesta Comprensión del enfoque de Mulmuley-Sohoni para P vs. NP , Regan:
también una sinopsis en la sección "¿Una nueva esperanza?" en Estado del problema P vs NP , Fortnow (2009)
[1] Explicación estilo Wikipedia de la teoría de la complejidad geométrica (tcs.se)
fuente
El siguiente resultado de Raz (Funciones evasivas y límites inferiores para circuitos aritméticos, STOC'08) está dirigido a (y no directamente a ), pero podría estar lo suficientemente cerca para el OP:P ≠ N PVPAGS≠ VnortePAGS PAGS≠ NPAGS
Un mapeo polinómico es -usivo, si para cada mapeo polinomial de grado , Imagen ( ) Imagen ( ). ( s , r ) Γ : F s → F m r f ⊄F: Fnorte→ Fmetro ( s , r ) Γ : Fs→ Fmetro r F ⊄ Γ
Para muchos ajustes de los parámetros , las construcciones explícitas de elusivos mapas polinómicos implican límites inferiores fuertes (hasta exponenciales) para los circuitos aritméticos generales.n , m , s , r
fuente
existe un campo de complejidad algo lateral / más recientemente estudiado llamado complejidad de gráfico que estudia cómo se construyen gráficos más grandes a partir de gráficos más pequeños utilizando operaciones AND y OR de bordes. Jukna tiene una buena encuesta . En particular, utilizando unidades de "gráficos de estrellas" hay un teorema clave, ver p20 comentario 1.18 (el teorema es técnicamente más fuerte que el siguiente y en realidad implica ):P≠NP/poly
fuente
¿Qué hay de Philip Maymin
"¿Los mercados son eficientes si y solo si P = NP " reclamo?
fuente
Los análogos de funciones de y ; y también serían interesantes en su estudio de la pregunta (?). Mientras que y son problemas de decisión que devuelven respuestas sí / no de bit, y realidad devuelven respuestas ( verifica las respuestas). Sabemos que , si . N P F P F N P P = N P P N P 1 F P F N P F N P F P = F N P P = N PP NP FP FNP P = NP P NP 1 FP FNP FNP FP = FNP P = NP
fuente