Un árbol de Pratt, para un n primo, es una representación estructurada, en forma de árbol (visualmente invertido), dónde el primer nodo es n y de él cuelgan otros nodos que son los factores primos de n-1.
Esta estructura fue presentada por Vaughan R. Pratt en el articulo “Every Prime Has a Succinct Certificate” publicado en 1.975 para usarlo junto con la prueba de E. Lucas y certificar que un número es primo.
Podemos obtener una medida de la complejidad del árbol a través de:
- El número total de nodos. Para el ejemplo 22 nodos.
- La altura del árbol, la longitud de la cadena principal más larga. Para el ejemplo 7 niveles.
La clase de complejidad de este árbol es NP .