Axiomes nécessaires à l'informatique théorique

Cette question est inspirée d'une question similaire sur les mathématiques appliquées sur mathoverflow, et cette pensée persistant pensait que des questions importantes du TCS telles que P vs NP pourraient être indépendantes de ZFC (ou d'autres systèmes). Comme arrière-plan, les mathématiques inversées sont le projet de recherche des axiomes nécessaires pour prouver certains théorèmes importants. En d'autres termes, nous commençons par un ensemble de théorèmes que nous espérons être vrais et essayons de dériver l'ensemble minimal d'axiomes «naturels» qui les rend tels.

Je me demandais si l'approche des mathématiques inversées avait été appliquée à des théorèmes importants du SDC. En particulier à la théorie de la complexité. Étant donné l’impasse sur de nombreuses questions en suspens dans TCS, il semble naturel de demander "quels axiomes n’avons-nous pas essayé de les utiliser?". Alternativement, des questions importantes dans TCS se sont-elles avérées indépendantes de certains sous-systèmes simples d'arithmétique de second ordre?

cc.complexity-theory lo.logic proof-complexity Artem Kaznatcheev
la source

Deux axiomes possibles qui peuvent ne pas être indépendants: 1) Le 3-SAT nécessite

temps. 2) Avec une formule 3SAT satisfiable, chaque algorithme efficace satisfait au maximum

fraction des clauses. En outre, il est difficile d’inverser (efficacement) la multiplication de deux nombres premiers de taille égale.

2^{Ω (n)}

$2^{\Omega(n)}$

7 / 8

$7/8$

Mohammad Al-Turkistany le

Cet article est pertinent: Harry Buhrman, Lance Fortnow, Leen Torenvliet, "Six hypothèses en quête d'un théorème", CCC, p. 2, 12e conférence annuelle de l'IEEE sur la complexité informatique (CCC'97), 1997

Mohammad Al-Turkistany

La question suivante est liée: cstheory.stackexchange.com/questions/1923/… La plupart des SDC peuvent être formalisés dans RCA_0. Le théorème mineur du graphe est une exception rare. Comme Neel le souligne, si vous voulez de nouvelles idées, cherchez de nouvelles idées; ne cherchez pas de nouveaux axiomes. Les deux ne sont pas du tout les mêmes.

Timothy Chow

Je ne comprends pas pourquoi les résultats tels que des déclarations sur

sont énoncés. Lors de ma première conférence sur le SDC, nous avons commencé avec des nombres naturels et quelques fonctions de base. Le reste suit. Apparemment je ne comprends pas la question.

P

$P$

N P

$NP$

Raphael

Je viens juste de remarquer cela, mais apparemment, Lipton a posé une question similaire dans ce message: rjlipton.wordpress.com/2011/02/03/… , pour citer: "Je me demande s’il existe des techniques de preuve impliquant des idées bien au-delà de la PA. pas utilisé, et qui aiderait à résoudre certains des problèmes importants. Devrions-nous enseigner à nos étudiants des cycles supérieurs des méthodes provenant de domaines de mathématiques qui se situent au-delà de l’AP? " (PA = Arithmétique Peano)

Artem Kaznatcheev

Réponses:

Oui, le sujet a été étudié dans la complexité des preuves. C'est ce qu'on appelle les mathématiques inversées bornées . Vous trouverez un tableau contenant certains résultats en mathématiques inversées à la page 8 du livre de Cook et Nguyen, " Fondements logiques de la complexité de la preuve ", 2010. Certains anciens étudiants de Steve Cook avaient déjà travaillé sur des sujets similaires, par exemple la thèse de Nguyen, " Bounded Reverse Mathematics ". Université de Toronto, 2008.

Alexander Razborov (également d'autres théoriciens de la complexité des preuves) a quelques résultats sur les théories faibles nécessaires pour formaliser les techniques de complexité des circuits et prouver les limites inférieures de la complexité des circuits. Il obtient des résultats non prouvables pour des théories faibles, mais les théories sont considérées comme trop faibles.

Tous ces résultats sont prouvables dans (théorie de base de Simpson pour les mathématiques inversées), de sorte que, autant que je sache, les résultats d'indépendance ne sont pas basés sur des théories fortes (et en fait, de tels résultats sur l'indépendance auraient des conséquences importantes, comme Neel l'a mentionné, voir Ben le travail de -David (et les résultats connexes) sur l' indépendance de de où est une extension de ). $RCA_0$ $\mathbf{P} vs. \mathbf{NP}$ $PA_1$ $PA_1$ $PA$

Kaveh
la source

De tels résultats en termes d’indépendance constitueraient des avancées majeures, mais je ne pense pas qu’ils aient des conséquences immédiates fortes; voir mon commentaire sur la réponse de Neel.

Timothy Chow

@ Tim, merci, vous avez raison, j'ai corrigé ma réponse. Ce n'est pas

P A

$PA$ , c'est

P A_{1}

$PA_1$ ,

P A

$PA$ étendu avec toutes les vraies phrases universelles d'arithmétique universelles, et Ben-David affirme que si la question est indépendante de cette théorie plus forte, SAT a un algorithme temporel presque polynomial. Donc, l'hypothèse est (beaucoup) plus forte mais la revendication finale est la même. (et les méthodes actuellement connues pour prouver son indépendance

P A

$PA$ impliquerait également l'indépendance de

P A_{1}

$PA_1$ .)

Kaveh

En guise de réponse positive à votre dernière question, les preuves de normalisation de calculs lambda polymorphes telles que le calcul de constructions nécessitent au moins une arithmétique supérieure, et des systèmes plus robustes (tels que le calcul de constructions inductives) sont équivalents avec ZFC ainsi que de nombreux autres inaccessibles.

En réponse négative à votre dernière question, Ben-David et Halevi ont montré que si $P \not= NP$ est indépendant de $PA_1$ , Arithmétique de Peano étendue avec des axiomes pour toutes les vérités arithmétiques universelles, il existe alors un algorithme presque polynomial $DTIME(n^{\log^{*}(n)})$ pour SAT. De plus, il n’existe actuellement aucun moyen connu de générer des phrases indépendantes de la $PA$ mais non $PA_1$ .

Plus philosophiquement, ne commettez pas l'erreur d'associer force de cohérence à la force d'une abstraction.

La manière correcte d’organiser un sujet peut impliquer des principes de théorie des ensembles apparemment sauvages, même s’ils ne sont peut-être pas strictement nécessaires en termes de force de consistance. Par exemple, les principes de collection forts sont très utiles pour énoncer des propriétés d'uniformité - par exemple, les théoriciens des catégories finissent par vouloir que les grands axiomes cardinaux faibles manipulent des choses comme la catégorie de tous les groupes comme s'il s'agissait d'objets. L'exemple le plus célèbre est la géométrie algébrique, dont le développement utilise largement les univers de Grothendieck, mais dont toutes les applications (comme le dernier théorème de Fermat) se situent apparemment dans l'arithmétique du troisième ordre. Comme exemple beaucoup plus trivial, notez que les opérations génériques d'identité et de composition ne sont pas des fonctions, car elles sont indexées sur tout l'univers des ensembles.

D’autre part, la relation entre force de la consistance et caractère abstrait va parfois dans le sens opposé. Considérez la relation entre les mesures et les mesures de motivation. Les mesures sont définies sur des familles de sous-ensembles ( $\sigma$ -algèbres) sur un ensemble $X$ , tandis que les mesures motiviques sont définies directement sur des formules interprétées $X$ . Ainsi, même si la mesure motivique généralise la mesure, la complexité de la théorie des ensembles diminue , puisqu'un usage de Powerset disparaît.

EDIT: le système logique A a une plus grande force de cohérence que le système B, si la cohérence de A implique la cohérence de B. Par exemple, ZFC a une résistance de cohérence supérieure à l'arithmétique Peano, car vous pouvez prouver la cohérence de PA dans ZFC. A et B ont la même force de consistance s’ils sont équiconsistants. Par exemple, l'arithmétique de Peano est cohérente si et seulement si l'arithmétique de Heyting (constructive) l'est.

OMI, l'un des faits les plus étonnants sur la logique est que la force de la cohérence se résume à la question "quelle est la fonction à la croissance la plus rapide que vous pouvez prouver totale dans cette logique?" En conséquence, la cohérence de nombreuses classes de logiques peut être ordonnée linéairement! Si vous avez une notation ordinale capable de décrire les fonctions dont la croissance est la plus rapide, vos deux logiques peuvent montrer un total, alors vous savez par trichotomie que l'une ou l'autre peut prouver la cohérence de l'autre, ou qu'elles sont équiconsistantes.

Mais ce fait étonnant explique également pourquoi la force de la cohérence n'est pas le bon outil pour parler d'abstractions mathématiques. C'est un invariant d'un système comprenant des astuces de codage, et une bonne abstraction vous permet d'exprimer une idée sans astuces. Cependant, nous n'en savons pas assez sur la logique pour exprimer cette idée de manière formelle.

Neel Krishnaswami
la source

Qu'est-ce que la "force de consistance"?

Suresh Venkat

Ce n'est pas ce que Ben-David et Halevi ont prouvé. Vous avez oublié leur coureur crucial, "en utilisant les techniques actuellement disponibles." J'interprète leur article en soulignant la faiblesse de nos techniques de preuve actuelles plutôt qu'en disant beaucoup sur la question P = NP.

Timothy Chow