Some Connection Between Mathematical Logic and Complexity Theory,

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1979
Accession Number
ADA071719

Entities

People

  • Richard A. Demillo
  • Richard J. Lipton

Organizations

  • Georgia Tech

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Arithmetic
  • Computational Complexity
  • Computations
  • Computer Science
  • Geometry
  • Language
  • Logic
  • Mathematical Logic
  • Mathematics
  • Number Theory
  • Plane Geometry
  • Polynomials
  • Set Theory
  • Standards
  • Theorems
  • Theoretical Computer Science

Fields of Study

  • Mathematics

Readers

  • Linear Algebra
  • Mathematical Modeling and Probability Theory.
  • Mental Health of Military Veterans with Posttraumatic Stress Disorder (PTSD): Risk Factors, Prevalence, Symptoms, and Treatment.