Some Connection Between Mathematical Logic and Complexity Theory.

摘要

The existence of lower bounds for problems in NP intersection coNP is equivalent to the existence of nonstandard, noneffective models of a fragment, PT, of complete arthmetic. A typical corrollary is that factoring integers is intractable if there is a model of arithmetic in which primes fail to have primitive roots. Following from the proof of the main result is an existential proof procedure for polynomial time algorithms. (Author)