La quantité maximale de ressource de type mémoire requise durant une preuve ou une réfutation, souvent formalisée comme le nombre maximal de formules, clauses ou lignes de preuve devant être simultanément conservées en mémoire selon un modèle de preuve donné.

Principe

Capture les besoins de stockage concurrent : l'espace de preuve mesure combien d'objets intermédiaires doivent être retenus au pic, reflétant des goulots d'étranglement mémoire indépendants du nombre total d'étapes.

Démonstration

Dans les modèles d'espace de clauses pour la résolution, l'espace de preuve compte le plus grand nombre de clauses qu'un algorithme de réfutation doit garder stockées à un moment donné ; des arguments de pebbling illustrent souvent des bornes inférieures sur l'espace de preuve.

Mauvaise application

Confondre l'espace de preuve avec l'empreinte mémoire totale d'une implémentation (qui inclut structures de données, index, cache) ou avec la taille de l'arbre de recherche conduit à une mauvaise planification des ressources ; l'espace est une métrique abstraite dépendante du modèle.

Conséquence

Des bornes inférieures élevées sur l'espace de preuve indiquent une difficulté mémoire inhérente à la réfutation dans le modèle et motivent des stratégies d'économie d'espace (par ex. politiques de suppression de clauses, preuves reprenables) ou le choix d'un autre système de preuve.

Inversion

Plutôt que de se concentrer sur le nombre maximal d'éléments concurrents, on peut mesurer le produit mémoire-temps cumulatif (l'intégrale de la mémoire sur le temps) pour capturer l'usage total de mémoire durant toute la preuve, ce qui déplace l'accent du pic vers le coût agrégé.

Limite

Dépend du modèle d'espace choisi (espace de clauses, espace de variables, espace de formules) et des hypothèses sur ce qui constitue du stockage et si la réutilisation ou la compression est permise ; n'inclut pas les ressources non mémoires comme le temps CPU sauf en combinaison.

Tension sémantique

Entre en tension avec la longueur et la largeur : des preuves courtes peuvent quand même exiger beaucoup d'espace, et minimiser l'espace peut contraindre à des preuves plus longues ; l'espace formalise un axe distinct de complexité.

Synthèse

L'espace de preuve est la métrique du pic de besoin mémoire qui, avec la longueur et la largeur, complète une triade de mesures orthogonales de complexité ; comprendre les compromis d'espace guide les algorithmes, structures de données et le choix de calculs de preuve pour gérer la pression mémoire.