 | Foram assinalados vários problemas nesta página ou se(c)ção: |
Em ciência da computação, complexidade de prova é a medida da eficiência dos métodos de prova de teoremas automatizados que é baseado no tamanho das provas que produzem. Os métodos para provar por contradição na lógica proposicional são os mais analisados, Os dois principais problemas considerados na complexidade de prova são se um método de prova pode produzir uma prova polinomial para toda fórmula inconsistente, e se as provas produzidas por um método são sempre de tamanho semelhante a aquelas produzidas por outro método.