DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
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
Distribution Statement:
APPROVED FOR PUBLIC RELEASE