Le nombre d'étapes d'inférence dans une dérivation ou preuve formelle au sein d'un système de preuve donné ; chaque étape est l'application d'une règle produisant une nouvelle formule ou séquent à partir des précédents.

Principe

Compte l'effort inférentiel séquentiel : des preuves plus courtes minimisent le nombre d'applications de règles nécessaires pour dériver une formule cible à partir de prémisses ou d'axiomes dans le système formel choisi.

Démonstration

En résolution propositionnelle, la longueur de preuve est le nombre d'étapes de résolution ou d'affaiblissement effectuées jusqu'à dériver la clause vide (réfutation), indépendamment de la taille des clauses intermédiaires.

Mauvaise application

Utiliser la longueur de preuve entre différents systèmes de preuve ou codages sans normalisation peut induire en erreur — certains systèmes autorisent de nombreuses petites étapes locales tandis que d'autres disposent de règles plus puissantes et moins nombreuses, rendant les comptages bruts incomparables.

Conséquence

Les bornes inférieures sur la longueur de preuve établissent des résultats de difficulté pour les prouveurs automatiques dans ce système ; trouver des preuves courtes permet une vérification plus rapide et oriente les heuristiques de recherche de preuve vers des dérivations concises.

Inversion

On peut inverser l'axe en mesurant la taille symbolique (taille de la preuve mesurée en nombre total de symboles ou bits) plutôt que le nombre d'étapes, ce qui met l'accent sur la complexité des formules par étape plutôt que sur le nombre d'étapes.

Limite

Définie relativement à un système de preuve spécifique, au choix des règles primitives et à la granularité de ce qui compte comme une étape ; exclut les ressources comme l'usage mémoire par étape et peut ne pas refléter l'inférence parallèle.

Tension sémantique

Entre en tension avec les mesures de largeur et d'espace : une preuve peut être courte mais large ou consommatrice d'espace, ainsi la longueur seule ne capture pas toutes les dimensions de complexité.

Synthèse

La longueur de preuve est une mesure linéaire du travail inférentiel dans un système formel ; combinée aux métriques de largeur et d'espace elle donne une vision multidimensionnelle de la complexité des preuves et éclaire les choix algorithmiques entre de nombreuses petites étapes et quelques règles complexes.