Axiomas necesarios para la informática teórica.

Esta pregunta está inspirada en una pregunta similar sobre las matemáticas aplicadas en el desbordamiento matemático, y ese fastidio pensó que las preguntas importantes de TCS como P vs. NP podrían ser independientes de ZFC (u otros sistemas). Como un poco de historia, la matemática inversa es el proyecto de encontrar los axiomas necesarios para probar ciertos teoremas importantes. En otras palabras, comenzamos con un conjunto de teoremas que esperamos sean verdaderos e intentamos derivar el conjunto mínimo de axiomas 'naturales' que los hacen así.

Me preguntaba si el enfoque matemático inverso se ha aplicado a algún teorema importante de TCS. En particular a la teoría de la complejidad. Con un punto muerto en muchas preguntas abiertas en TCS, parece natural preguntarse "¿qué axiomas no hemos intentado usar?". Alternativamente, ¿se ha demostrado que alguna pregunta importante en TCS es independiente de ciertos subsistemas simples de aritmética de segundo orden?

cc.complexity-theory lo.logic proof-complexity Artem Kaznatcheev
fuente

Dos posibles axiomas que pueden no ser independientes: 1) 3-SAT requiere

tiempo. 2) Dado fórmula 3SAT satisfiable, cada eficientes satisface algoritmo a lo sumo

-fraction de las cláusulas. Además, la multiplicación de dos primos de igual tamaño es difícil de invertir (eficientemente).

2^{Ω (n)}

$2^{\Omega(n)}$

7 / 8

$7/8$

Mohammad Al-Turkistany

Este documento es relevante: Harry Buhrman, Lance Fortnow, Leen Torenvliet, "Seis hipótesis en busca de un teorema", CCC, pp.2, 12ª Conferencia Anual IEEE sobre Complejidad Computacional (CCC'97), 1997

Mohammad Al-Turkistany

La siguiente pregunta está relacionada: cstheory.stackexchange.com/questions/1923/… La mayoría de los TCS se pueden formalizar en RCA_0. El teorema menor del gráfico es una rara excepción. Como enfatiza Neel, si desea nuevas ideas, busque nuevas ideas; no busques nuevos axiomas. Los dos no son para nada iguales.

Timothy Chow

Estoy confundido por qué se indican resultados como declaraciones sobre

En mi primera conferencia TCS, comenzamos con números naturales y algunas funciones básicas sobre ellos. El resto sigue. Aparentemente no entiendo la pregunta.

P

$P$

N P

$NP$

Raphael

Acabo de notar esto, pero aparentemente Lipton hizo una pregunta similar en esta publicación: rjlipton.wordpress.com/2011/02/03/… , para citar: "Me pregunto si hay técnicas de prueba que involucren ideas mucho más allá de la AP que tenemos no utilizado, y lo que ayudaría a abrir algunos de los problemas importantes. ¿Deberíamos enseñar a nuestros estudiantes de posgrado métodos de áreas de matemáticas que se encuentran más allá de la AP? " (PA = Aritmética de Peano)

Artem Kaznatcheev

Respuestas:

Sí, el tema ha sido estudiado en pruebas de complejidad. Se llama Matemática inversa limitada . Puede encontrar una tabla que contiene algunos resultados de matemática inversa en la página 8 del libro de Cook y Nguyen, " Fundamentos lógicos de la complejidad de la prueba ", 2010. Algunos de los estudiantes anteriores de Steve Cook han trabajado en temas similares, por ejemplo, la tesis de Nguyen, " Matemática inversa limitada ". , Universidad de Toronto, 2008.

Alexander Razborov (también otros teóricos de la complejidad de la prueba) tiene algunos resultados sobre las teorías débiles necesarias para formalizar las técnicas de complejidad del circuito y probar los límites más bajos de la complejidad del circuito. Obtiene algunos resultados de improbabilidad para teorías débiles, pero las teorías se consideran demasiado débiles.

Todos estos resultados son demostrables en (teoría básica de Simpson para Matemática Inversa), por lo que AFAIK no tenemos resultados de independencia de teorías sólidas (y de hecho, tales resultados de independencia tendrían fuertes consecuencias como Neel ha mencionado, ver Ben -Trabajo de David (y resultados relacionados) sobre la independencia de de donde es una extensión de ). $RCA_0$ $\mathbf{P} vs. \mathbf{NP}$ $PA_1$ $PA_1$ $PA$

Kaveh
fuente

Tales resultados de independencia serían avances importantes, pero no creo que tengan consecuencias fuertes inmediatas; mira mi comentario sobre la respuesta de Neel.

Timothy Chow

P A

$PA$

P A_{1}

$PA_1$

P A

$PA$

P A

$PA$

P A_{1}

$PA_1$

Como respuesta positiva a su pregunta final, las pruebas de normalización de cálculos lambda polimórficos como el cálculo de las construcciones requieren al menos una aritmética de orden superior, y los sistemas más fuertes (como el cálculo de las construcciones inductivas) son equiconsistentes con ZFC más innumerables inaccesibles.

$P \not= NP$ $PA_1$ $DTIME(n^{\log^{*}(n)})$ $PA$ $PA_1$ .

Más filosóficamente, no cometa el error de equiparar la fuerza de consistencia con la fuerza de una abstracción.

La forma correcta de organizar un tema puede involucrar principios de teoría de conjuntos aparentemente salvajes, aunque pueden no ser estrictamente necesarios en términos de consistencia. Por ejemplo, los principios de recopilación sólidos son muy útiles para establecer propiedades de uniformidad; por ejemplo, los teóricos de categoría terminan queriendo axiomas cardinales grandes y débiles para manipular cosas como la categoría de todos los grupos como si fueran objetos. El ejemplo más famoso es la geometría algebraica, cuyo desarrollo hace un uso extensivo de los universos de Grothendieck, pero todas cuyas aplicaciones (como el último teorema de Fermat) aparentemente se encuentran dentro de la aritmética de tercer orden. Como un ejemplo mucho más trivial, tenga en cuenta que la identidad genérica y las operaciones de composición no son funciones, ya que están indexadas en todo el universo de conjuntos.

$\sigma$ $X$ $X$

EDITAR: el sistema lógico A tiene una mayor resistencia de consistencia que el sistema B, si la consistencia de A implica la consistencia de B. Por ejemplo, ZFC tiene una mayor resistencia de consistencia que la aritmética de Peano, ya que puede probar la consistencia de PA en ZFC. A y B tienen la misma fuerza de consistencia si son equiconsistentes. Como ejemplo, la aritmética de Peano es consistente si y solo si la aritmética de Heyting (constructiva) lo es.

En mi opinión, uno de los hechos más sorprendentes sobre la lógica es que la fuerza de la consistencia se reduce a la pregunta "¿cuál es la función de más rápido crecimiento que puede demostrar total en esta lógica?" Como resultado, la consistencia de muchas clases de lógicas se puede ordenar linealmente. Si tiene una notación ordinal capaz de describir las funciones de crecimiento más rápido que sus dos lógicas pueden mostrar en total, entonces sabe por tricotomía que una puede probar la consistencia de la otra o son equiconsistentes.

Pero este hecho sorprendente también es la razón por la cual la fuerza de consistencia no es la herramienta adecuada para hablar de abstracciones matemáticas. Es un sistema invariable que incluye trucos de codificación, y una buena abstracción le permite expresar una idea sin trucos. Sin embargo, no sabemos lo suficiente sobre lógica para expresar esta idea formalmente.

Neel Krishnaswami
fuente

¿Qué es la "fuerza de consistencia"?

Suresh Venkat

Eso no fue lo que probaron Ben-David y Halevi. Pasó por alto a su jinete crucial, "utilizando las técnicas disponibles actualmente". Interpreto que su trabajo enfatiza cuán débiles son nuestras técnicas de prueba actuales en lugar de decir mucho sobre la pregunta P = NP.

Timothy Chow