Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/7030
Title: Finitely Presented Algebras and the Polynomial Time Hiercharchy
Authors: Kozen, Dexter
Keywords: computer science
technical report
Issue Date: Mar-1977
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR77-303
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].
URI: http://hdl.handle.net/1813/7030
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
77-303.pdf929.21 kBAdobe PDFView/Open
77-303.ps401.89 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us