Una forma de probar NP coNP es mostrar que para cada sistema de prueba proposicional f computable en tiempo polinómico, existe una familia de tautologías para las cuales f requiere longitudes de prueba súper polinomiales (wrt la longitud de la tautología que se está probando). Resultados como el de Haken y Ajtai arreglan un sistema de prueba proposicional y prueban que cierta familia (PHP en este caso) requiere pruebas de longitud súper polinomiales.
Mi pregunta: ¿Hay resultados que no arreglan un sistema de prueba y muestran, posiblemente, límites inferiores muy débiles, pero no triviales en la longitud de la prueba? Por ejemplo: ¿Hay resultados que muestren que para cada sistema de prueba proposicional, existe una familia de tautologías que requiere longitudes de prueba superlineales?