Exemple d'algorithme dépourvu de preuve d'exactitude

18

Nous avons la logique Hoare. Pourquoi est-il toujours possible qu'un algorithme soit correct mais il n'y a aucune preuve qu'il est correct? Supposons que l'algorithme soit exprimé en C. Ensuite, nous pouvons affirmer étape par étape qu'il fait ce qu'il est censé faire.

Ma question est donc:

Donnez-moi un exemple d'algorithme qui est juste mais qui n'a pas de preuve d'exactitude.

EDIT: Je pense qu'un petit historique peut aider à clarifier où je vais. Permettez-moi de citer Scott Aaronson:

Depuis les années 1970, il y a eu des spéculations selon lesquelles P NP pourrait être indépendant (c'est-à-dire ni prouvable ni réfutable) des systèmes d'axiomes standard pour les mathématiques, tels que la théorie des ensembles de Zermelo-Fraenkel. Pour être clair, cela signifierait que soit $\ne$

il n'existe pas d'algorithme en temps polynomial pour les problèmes NP-complets, mais nous ne pouvons jamais le prouver (du moins pas dans nos systèmes formels habituels), sinon

il existe un algorithme en temps polynomial pour les problèmes NP-complets , mais soit nous ne pouvons jamais prouver qu'il fonctionne, soit nous ne pouvons jamais prouver qu'il s'arrête en temps polynomial.

Je fais référence à la deuxième possibilité. Étant donné qu'Aaronson peut en toute confiance l'énumérer comme une possibilité, je pense qu'il doit y avoir un exemple existant de type 2. C'est pourquoi je pose cette question. Mais il ne semble pas qu'une réponse rapide et claire soit en vue.

correctness-proof hoare-logic Zirui Wang
la source

17

Que signifie dire qu'un algorithme est correct si nous n'avons pas de preuve d'exactitude?

David Richerby

14

Voulez-vous dire "la preuve de l'exactitude est impossible" ou "personne n'a prouvé qu'elle était correcte"?

gnasher729

12

Les algorithmes n'ont pas à être corrects ... supposons que vous ayez ceci: (1) mettez un seau vide sur le rebord de la fenêtre le matin. (2) le retirer le soir. (3) mesurer le volume d'eau dans le seau. (4) répéter le lendemain matin. Ceci est une description d'un algorithme, mais il ne décrit rien qui puisse être, sans étirement, appelé "correct". Fait intéressant, la plupart des codes de programmation dans le monde sont écrits de cette manière particulière: ils ne sont tout simplement pas concernés par l'exactitude de ce qu'ils font.

wvxvw

@wvxvw Je suis confus alors, qu'est-ce que cela signifie pour un algorithme d'être "correct" alors? S'il fait ce qu'il était censé faire, cela ne signifie-t-il pas que c'est correct? Si l'objectif de votre scénario était de trouver la quantité moyenne d'eau collectée dans le seau pendant les précipitations, pour chaque jour, l'algorithme ne serait-il pas correct dans ce cas?

Abdul

8

@chi vous ne comprenez pas ... ce n'est pas que les programmeurs ne se soucient pas de la justesse de leur code, c'est que pour certains algorithmes le concept de "justesse" n'est pas applicable. Prenez une application .NET WindowsForms, qui dit quelque chose à l'effet: "placez ce bouton avec cette étiquette à cette position, puis placez cet autre bouton à cette autre position et ainsi de suite ..." - il pourrait y avoir une interprétation de ce que cela programme, en vertu duquel ce qu'il fait peut être jugé comme (in) correct (par exemple, le graphiste dit qu'il "semble moche"), mais c'est aussi loin que cela va.

wvxvw

50

Voici un algorithme pour la fonction d'identité:

Entrée: $n$
Vérifiez si la ème chaîne binaire code une preuve de dans ZFC, et si c'est le cas, sortez $n$ $0 > 1$ $n+1$
Sinon, sortie $n$

La plupart des gens soupçonnent que cet algorithme calcule la fonction d'identité, mais nous ne savons pas, et nous ne pouvons pas le prouver dans le cadre communément admis pour les mathématiques, ZFC .

Yuval Filmus
la source

2

Êtes-vous sûr de vérifier si la ème chaîne binaire code une preuve de dans ZFC $n$ $0 > 1$ est un algorithme?

Dmitry Grigoryev

23

Non, mais la vérification peut certainement être implémentée de manière algorithmique (c'est-à-dire par une machine de Turing). En fait, c'est l'une des exigences que nous avons pour les systèmes de preuve - que la validité de la preuve soit vérifiable par algorithme.

Yuval Filmus

6

@Puppy ZFC prouve

. Mais il pourrait également s'avérer

si (f) il est incohérent. Presque tout le monde croit que ZFC est cohérent, bien sûr, mais à cause des théorèmes d'incomplétude, nous ne pouvons pas le savoir avec certitude.

\neg (0 > 1)

$\lnot (0>1)$

0 > 1

$0>1$

chi

1

@Nathaniel Pas du tout. Vous pouvez facilement prouver l'exactitude de chaque algorithme de manuel, par exemple. Cet algorithme diffère en ce qu'il repose sur la cohérence de ZFC, ce que ZFC lui-même ne peut pas prouver.

Yuval Filmus

1

@Nathaniel: Si vous le souhaitez, laissez-nous poursuivre cette discussion dans le chat .

user21820

9

La plupart des algorithmes ne se sont pas révélés corrects dans la logique Hoare. La raison principale est que de telles preuves de correction sont extrêmement coûteuses en janvier 2017, probablement de plusieurs ordres de grandeur par rapport à une `` simple '' programmation. Il y a beaucoup de travail en cours pour réduire ce coût par l'automatisation, mais c'est une lutte difficile.

Une autre raison pour laquelle un algorithme pourrait ne pas avoir de preuve d'exactitude, et qui est plus pertinente dans la pratique que les phénomènes d'incomplétude mentionnés par Yuval et chi, est que nous ne savons peut-être pas ce qu'est cette spécification. Ce problème a deux dimensions.

Les clients ne savent pas ce qu'ils veulent. Il s'agit d'un problème bien connu en génie logiciel, et les ingénieurs logiciels ont développé de nombreuses approches pour y faire face.
$n$ allant sur des nombres naturels, et les adversaires sont des machines de Turing probabilistes à temps polynomial. À ma connaissance (veuillez me corriger si je me trompe), il existe un décalage entre la théorie et la pratique, et les algorithmes concrets comme AES et SHA256 ne sont pas tout à fait dans le champ d'application de ces spécifications théoriques. Je ne pense pas qu'il existe une spécification complète pour de tels algorithmes, donc nous ne pouvons pas, en principe, les vérifier dans le sens, par exemple, de la logique de Hoare.

Martin Berger
la source

AES relève de la définition de la sécurité cryptographique. (Vous devez utiliser des définitions de sécurité concrètes plutôt que des définitions asymptotiques, mais vous devriez quand même le faire si vous voulez la sécurité dans la pratique.)

DW

@DW Intéressant. Je n'étais pas au courant. Comment la nature asymptotique de la cryptographie théorique est-elle contournée? Pouvez-vous s'il vous plaît me diriger vers un document à ce sujet? Qu'en est-il des fonctions de hachage cryptographiques concrètes?

Martin Berger

en.wikipedia.org/wiki/Concrete_security et les références qui y sont répertoriées. Les fonctions de hachage sont un cas plus complexe, car cela dépend de leur utilisation - mais les complexités sont largement orthogonales à la sécurité asymptotique par rapport à la sécurité concrète.

DW

2

Pour le chiffrement, vous avez besoin de deux algorithmes: l'un qui chiffre, l'autre qui déchiffre. L'un d'eux ne peut pas être correct à lui seul. Ils ne peuvent être corrects que par paire (vous prouvez que le décryptage d'une entrée cryptée produit l'original). Mais pour le chiffrement, vous voulez qu'il ne soit pas craquable et c'est quelque chose que vous ne pouvez pas attraper avec "exactitude".

gnasher729

1

@DW Je dois être quelque peu en désaccord. Bien que les articles de Rogaway et Bellare soient excellents, ce qui implique qu'ils permettent en aucune façon des preuves de sécurité des primitives est trompeur. Les deux articles portent essentiellement sur les protocoles (c'est-à-dire qu'ils supposent que les primitives telles que AES, SHA, RSA, etc.) sont sécurisées et prouvent ensuite les choses à partir de là. Le problème essentiel de la sécurisation des primitives elles-mêmes demeure. Si vous avez des références pour des preuves de sécurisation de primitives, je serais intéressé. Le deuxième article, par exemple, suppose que RSA est difficile, ce qui est un problème ouvert.

DRF

5

\frac{P ⟹ P^{'} {P^{'}} c {Q^{'}} Q^{'} ⟹ Q^{'}}{{P} c {Q}}

$\dfrac{ P \implies P' \qquad \{P'\}c\{Q'\} \qquad Q' \implies Q' }{ \{P\}c\{Q\} }$

P ⟹ P^{'}, Q ⟹ Q^{'}

$P\implies P', Q\implies Q'$

$P(n)$ $P(0)$ $P(1)$ $P(2)$ $\forall n\in \mathbb{N}.\ P(n)$

$M$ $n$ $P(n)$ $M$ $\forall n.\ P(n)$ $M$ $\forall n.\ P(n)$

chi
la source

5

Problème: Imprimez "Oui" si chaque nombre pair ≥ 4 est la somme de deux nombres premiers et "Non" s'il y a un nombre pair ≥ 4 qui n'est pas la somme de deux nombres premiers.

Algorithme: imprimer "Oui"

La plupart des gens pensent que l'algorithme est correct. Il n'y a pas de preuve connue, et il est fort possible qu'il n'y ait pas de preuve.

gnasher729
la source

3

Tout algorithme qui est correct mais nous ne savons pas combien de temps il faut pour l'exécuter peut être transformé en un algorithme qui s'arrête dans un laps de temps garanti, mais nous ne savons pas s'il est correct.

$n$ $n+1$ $0$ $\log(n)^2$ $0$ $\sqrt{n}$

$P=NP$

Dan Brumleve
la source

Exemple d'algorithme dépourvu de preuve d'exactitude

Réponses: