El número de pasos de inferencia en una derivación o prueba formal dentro de un sistema de prueba especificado; cada paso es la aplicación de una regla que produce una nueva fórmula o secuencia a partir de anteriores.

Principio

Cuenta el esfuerzo inferencial secuencial: las pruebas más cortas minimizan el número de aplicaciones de reglas necesarias para derivar una fórmula objetivo a partir de premisas o axiomas en el sistema formal elegido.

Demostración

En resolución proposicional, la longitud de la prueba es el número de pasos de resolución o debilitamiento realizados hasta derivar la cláusula vacía (refutación), independientemente del tamaño de las cláusulas intermedias.

Aplicación incorrecta

Usar la longitud de la prueba entre diferentes sistemas de prueba o codificaciones sin normalización puede ser engañoso: algunos sistemas permiten muchos pasos locales pequeños mientras otros usan reglas menos pero más potentes, haciendo incomparables los recuentos brutos.

Consecuencia

Cotas inferiores sobre la longitud de la prueba establecen resultados de dureza para los demostradores automáticos en ese sistema; encontrar pruebas cortas permite verificaciones más rápidas y guía heurísticas de búsqueda hacia derivaciones concisas.

Inversión

Se puede invertir el enfoque y medir el tamaño simbólico (tamaño de la prueba medido en el número total de símbolos o bits) en lugar del recuento de pasos, enfatizando la complejidad de las fórmulas por paso.

Límite

Definida en relación con un sistema de prueba específico, la elección de reglas primitivas y la granularidad de lo que cuenta como paso; excluye recursos como el uso de memoria por paso y puede no reflejar la inferencia paralela.

Tensión semántica

En tensión con medidas como anchura y espacio: una prueba puede ser corta pero ancha o intensiva en espacio, por lo que la longitud por sí sola no captura todas las dimensiones de complejidad.

Síntesis

La longitud de la prueba es una medida lineal del trabajo inferencial en un sistema formal; combinada con métricas de anchura y espacio proporciona una visión multidimensional de la complejidad de las pruebas e informa decisiones algorítmicas sobre compensaciones entre muchos pasos pequeños y pocas reglas complejas.