Accession Number:

ADA071719

Title:

Some Connection Between Mathematical Logic and Complexity Theory,

Descriptive Note:

Corporate Author:

GEORGIA INST OF TECH ATLANTA SCHOOL OF INFORMATION AND COMPUTER SCIENCE

Report Date:

1979-04-01

Pagination or Media Count:

24.0

Abstract:

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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE