The Complexity of Provable Properties of First Order Theories,

Abstract

This paper considers first order quantified and modal theories with the interpretation of function and predicate symbols restricted to fixed r.e. sets of functions F and predicates R. We characterize functions with certain properties (such as totality, monotonicity, unboundedness) provable in these theories. In the case F and R are restricted to a complexity class (such as polynomial time), our results give a characterization of complexity hierarchies (such as the polynomial time hierarchy of Stockmeyer in terms of strength of theories whose axioms have restricted quantification. In addition we construct formulas for which probability in these theories implies the collapse of the corresponding complexity hierarchy. We consider modal theories as well as purely quantified theories. Because modal formulas can encode arbitrary alternations of quantifiers, probability of certain formulas in these modal theories implies the collapse of complexity hierarchies with unbounded alternation. This is applied to the P = (questionably) PSPACE problem. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1980
Accession Number
ADA095656

Entities

People

  • John Reif
  • Steve Homer

Organizations

  • Harvard University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Arithmetic
  • Collapse
  • Computer Science
  • Exponential Functions
  • Hierarchies
  • Language
  • Logic
  • Mathematical Logic
  • Mathematics
  • Military Research
  • Number Theory
  • Numbers
  • Polynomials
  • Recursive Functions
  • Standards
  • Theorems

Fields of Study

  • Mathematics

Readers

  • Mathematical Modeling and Probability Theory.