Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Finitely Presented Algebras and the Polynomial Time Hiercharchy

Finitely Presented Algebras and the Polynomial Time Hiercharchy

File(s)
77-303.ps (401.89 KB)
77-303.pdf (929.21 KB)
Permanent Link(s)
https://hdl.handle.net/1813/7030
Collections
Computer Science Technical Reports
Author
Kozen, Dexter
Abstract

Let $S_{n}(V_{n})={less than \Gamma, Q_{1}v_{1}\cdots Q_{k}v_{k} s \equiv j greater than | \Gamma$ is a finite presentation of $\cal A, Q_{1} \cdots Q_{k}$ is a string of quantifiers with $n$ alterations, the outermost an $\exists (\forall), \cal A \Gamma Q_{1} v_{1} \cdots Q_{k} v_{k} s \equiv t}$. It is shown that $S_{n} (V_{n})$ is complete for $\Sigma^{P}{n} (\Pi^{P}{n})$, and $\stackrel{\stackrel{\infty}{\bigcup}}{n=0} S_{n} \cup V_{n}$ is complete for PSPACE, answering a question of [1] and generalizing a result of Stockmeyer and Meyer [2].

Date Issued
1977-03
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR77-303
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance