Exposição Limitada, Testemunhas Eficazes e os Limites Estruturais da Computação em Tempo Polinomial

Este artigo desenvolve uma estrutura para a computação em tempo polinomial baseada em exposição limitada e testemunhas de incompatibilidade efetivas. Baseando-se em resultados anteriores que descartaram algoritmos não adaptativos e ligaram a NP-dificuldade a dependências irreduzíveis globais, prova que toda computação determinística em tempo polinomial admite uma forma normal de exposição limitada e introduz o princípio da Exposição Limitada Forte com Testemunhas Eficazes. Este princípio afirma que a rejeição deve ser acompanhada por um certificado finito, local e extraível. Através de tentativas sistemáticas de refutar esta hipótese em paradigmas combinatórios, algébricos, espectrais e estatísticos, o artigo não encontra contraexemplos. A estrutura reduz o problema P versus NP a se problemas NP-completos admitem dependências irreduzíveis globais que evitam todas as testemunhas efetivas.