Existe-t-il des lois de conservation dans la théorie de la complexité?

Permettez-moi de commencer par quelques exemples. Pourquoi est-il si simple de montrer que CVP est dans P mais si difficile de montrer que LP est dans P; alors que les deux sont des problèmes P-complets.

Ou prenez la primalité. Il est plus facile de montrer des composites en NP que des nombres premiers en NP (qui nécessitait Pratt) et éventuellement en P. Pourquoi devait-il afficher cette asymétrie?

Je connais Hilbert, le besoin de créativité, les preuves sont en NP, etc. Mais cela ne m'a pas empêché d'avoir mal à l'aise en pensant qu'il y a plus que cela à première vue.

Existe-t-il une notion quantifiable de "travail" et de "loi de conservation" dans la théorie de la complexité? Cela montre, par exemple, que même si CVP et LP sont tous deux P-complets, ils cachent leur complexité à des "endroits différents" - un dans la réduction (Le CVP est-il simple parce que tout le travail est fait dans la réduction?) autre dans l’expression de la langue.

Quelqu'un d'autre a-t-il des nausées et des idées? Ou alors haussons-nous les épaules et disons / acceptons que c'est la nature du calcul?

Ceci est ma première question sur le forum: les doigts croisés.

Edit: CVP est un problème de valeur de circuit et LP est une programmation linéaire. Merci Sadeq, pour avoir signalé une confusion.

C’est une question qui m’a traversé l’esprit plusieurs fois.

Je pense qu'un des endroits à regarder est la théorie de l'information. Voici une de mes spéculations. Étant donné un problème, nous pouvons peut-être attribuer une sorte d'entropie aux informations données en entrée et aux informations reçues de l'algorithme. Si nous pouvions le faire, un algorithme gagnerait un minimum d’informations pour résoudre ce problème.

Il y a une chose en rapport que je voulais comprendre. Dans certains problèmes NP-complets, vous pouvez trouver une version contrainte dans P; avec le chemin hamiltonien si vous spécifiez que le graphique est un DAG, il existe un algorithme p-time pour le résoudre. Avec d'autres problèmes comme TSP, il existe souvent des algorithmes p-time qui se rapprochent de l'optimum. Il me semble que, pour les algorithmes p-temps limités, il devrait exister une relation proportionnelle entre les informations d'addition supposées et la réduction de la complexité à l'exécution. Dans le cas du TSP, nous n'assumons pas d'informations supplémentaires, nous atténuons la précision, ce qui, je suppose, aurait un effet similaire sur tout type de gain d'informations algorithmiques.

Note sur les lois de conservation

Au début des années 1900, Emily Noether, mathématicienne germano-américaine, était peu connue. Einstein et Hilbert ont décrit entre autres choses les femmes les plus importantes de l'histoire des mathématiques. En 1915, elle publia ce qu'on appelle aujourd'hui le premier théorème de Noether . Le théorème concernait les lois physiques de la conservation et indiquait que toutes les lois de la conservation avaient une symétrie différentielle correspondante dans le système physique. La conservation de la quantité de mouvement angulaire provient d’une symétrie de rotation dans l’espace. La conservation de la quantité de mouvement linéaire est une translation dans l’espace. La conservation de l’énergie est une translation dans le temps. Étant donné que, pour qu'il y ait une loi de conservation de la complexité au sens formel, il faudrait qu'il y ait une symétrie différentielle correspondante dans une fonction langragienne.

Je pense que la raison réside dans le système logique que nous utilisons. Chaque système formel a un ensemble d' axiomes et un ensemble de règles d'inférence .

Une preuve dans un système formel est simplement une séquence de formules telle que chaque formule de la séquence est un axiome ou est obtenue à partir de formules précédentes de la séquence en appliquant une règle d'inférence. Un théorème du système formel n'est que la dernière formule d'une preuve.

La longueur de la preuve d'un théorème, en supposant qu'il soit décidable dans le système logique, dépend totalement des ensembles d' axiomes et des règles d'inférence .

Par exemple, considérons la logique propositionnelle, pour laquelle il existe plusieurs caractérisations: Frege (1879), Nicod (1917) et Mendelson (1979). (Voir cette courte enquête pour plus d'informations.)

$\varphi \to \varphi$

Ce problème est appelé complexité de la preuve . Pour citer Beame & Pitassi :

L'une des questions les plus fondamentales de la logique est la suivante: Dans le cas d'une affirmation universellement vraie (tautologie), quelle est la longueur de la preuve la plus courte de l'affirmation dans un système de preuve axiomatique standard? La version à logique propositionnelle de cette question est particulièrement importante en informatique pour la démonstration de théorèmes et la théorie de la complexité. Les questions algorithmiques connexes importantes sont les suivantes: Existe-t-il un algorithme e cient qui produira une preuve de toute tautologie? Existe-t-il un algorithme efficace pour produire la preuve la plus courte de toute tautologie? Cette question de démonstration de théorème et de complexité a inspiré le document fondamental de Cook sur la NP-complétude intitulé notamment «La complexité des procédures de démonstration de théorèmes» et avait déjà été envisagé par Gödel dans sa lettre désormais bien connue à von Neumann.

Je réfléchissais à la même question l'autre jour, lorsque je rejouais certaines conférences de Feynman sur la physique et que je passais à la leçon 4 sur la conservation de l'énergie. Dans la conférence, Feynman utilise l’exemple d’une machine simple qui (grâce à un système de leviers, de poulies ou autre) réduit le poids d’une unité d’une distance x et l’utilise pour lever un deuxième poids de 3 unités. À quelle hauteur le poids peut-il être soulevé? Feynman fait observer que si la machine est réversible, nous n’avons donc pas besoin de connaître le mécanisme de la machine - nous pouvons la traiter comme une boîte noire - et elle soulèvera toujours le poids le plus loin possible ( x / 3 dans ce cas).

Est-ce que cela a un analogue dans le calcul? L'idée du calcul réversible rappelle les travaux de Landauer et Bennett, mais je ne suis pas sûre que ce soit le sens du terme qui nous intéresse. Intuitivement, si nous avons un algorithme optimal pour un problème donné, aucun «travail» inutile ne sera effectué en faisant tourner des bits; Une approche brutale du même problème consisterait à jeter les cycles du processeur à gauche et à droite. Cependant, j'imagine que l'on pourrait construire un circuit physiquement réversible pour l'un ou l'autre algorithme.

Je pense que la première étape pour aborder une loi de conservation concernant la complexité informatique consiste à déterminer exactement ce qui doit être conservé. L'espace et le temps sont chacun des paramètres importants, mais l'existence de compromis entre l'espace et le temps montre clairement que ni l'un ni l'autre ne suffiront à eux seuls pour mesurer le "travail" réalisé par un algorithme. Il existe d'autres paramètres, tels que les inversions de tête de MT ou les passages de cellules de bande utilisés. Aucun de ceux-ci ne semble vraiment être proche de notre intuition de la quantité de "travail" nécessaire pour effectuer un calcul.

Le revers de la médaille est de savoir en quoi ce travail est converti. Une fois que vous avez la sortie d'un programme, qu'est-ce que vous avez gagné exactement?

Quelques observations suggérant l'existence d'une loi de conservation:

$<_p$$P\ne NP$

$P=\{L| L<_p HornSAT \}$

$NP=\{L| L<_p 3SAT \}$

$CoNP=\{L| \bar L<_p 3SAT \}$

$NPC=\{L| L<_p 3SAT, 3SAT<_p L \}$

$PC=\{L| L<_p HornSAT, HornSAT<_p L \}$

EDIT :$P$$P=\{L| L<_p HornSAT, \bar L <_p HornSAT \}$$P$$NP$$P=NP$

Tao suggère l'existence d'une loi de conservation difficile en mathématiques: "afin de prouver tout résultat réellement non trivial, un travail difficile doit être effectué quelque part".

Il soutient que la difficulté de certaines preuves mathématiques suggère une limite inférieure à la quantité d'effort requise par le processus de démonstration de théorème.