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

Personal Author(s):

• DeMillo,Richard A.
• Lipton,Richard J.

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

Descriptors:

• *MATHEMATICAL LOGIC
• ALGORITHMS
• LINEAR PROGRAMMING
• POLYNOMIALS
• COMBINATORIAL ANALYSIS
• SET THEORY

Subject Categories:

• Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE