Affordable Access

Publisher Website

Applicative theories for the polynomial hierarchy of time and its levels

Authors
Journal
Annals of Pure and Applied Logic
0168-0072
Publisher
Elsevier
Volume
164
Issue
6
Identifiers
DOI: 10.1016/j.apal.2012.05.006
Keywords
  • Computational Complexity
  • Polynomial Hierarchy
  • Levels Of The Polynomial Hierarchy
  • Applicative Theories
  • Induction Schemes

Abstract

Abstract In this paper we introduce applicative theories which characterize the polynomial hierarchy of time and its levels. These theories are based on a characterization of the functions in the polynomial hierarchy using monotonicity constraints, introduced by Ben-Amram, Loff, and Oitavem.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

The polynomial-time hierarchy

on Theoretical Computer Science Jan 01, 1976

The Suslin operator in applicative theories: Its p...

on Annals of Pure and Applied Log... Jan 01, 2011

On collapsing the polynomial-time hierarchy

on Information Processing Letters Jan 01, 1994

On counting problems and the polynomial-time hiera...

on Theoretical Computer Science Jan 01, 1980
More articles like this..