The polynomially exponential time restrained analytical hierarchy

DOI10.1007/BF02945517MaRDI QIDQ1337640zbMATH OpenOpenAlexFDO

Authors Yuefei Sui

Publication date 7 June 1995

Published in Journal of Computer Science and Technology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02945517

zbMATH Keywords

deterministic Turing machineoraclepolynomial timepolynomially analytical hierarchypolynomially exponential time

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

The author defines a \(p\)-analytical hierarchy of relations \(\Sigma^{1,p} [n]\) and \(\Pi^{1,p} [n]\) making some mistakes through carelessness in definitions. A series of simple properties of the hierarchy are given generalizing those of the well-known analytical hierarchy. Then the author shows that there exists a (recursive) oracle \(A\) such that the sentence `\(\Sigma^{1,p} [n] [A]= \Sigma^{1,p} [n+1] [A]\)' is neither provable nor disprovable in ZF.

Recommendations

• The Analytic Polynomial-Time Hierarchy
• Publication:4936674
• Bounding queries in the analytic polynomial-time hierarchy
• The polynomial-time hierarchy and oracle set \(A \in \text{PH/poly}\)
• On Relativized Polynomial and Exponential Computations

Cited in

(1)

• The Analytic Polynomial-Time Hierarchy

This page was built for publication: The polynomially exponential time restrained analytical hierarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1337640)