The polynomially exponential time restrained analytical hierarchy (Q1337640)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The polynomially exponential time restrained analytical hierarchy |
scientific article; zbMATH DE number 683608
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The polynomially exponential time restrained analytical hierarchy |
scientific article; zbMATH DE number 683608 |
Statements
The polynomially exponential time restrained analytical hierarchy (English)
0 references
7 June 1995
0 references
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.
0 references
deterministic Turing machine
0 references
polynomial time
0 references
polynomially exponential time
0 references
polynomially analytical hierarchy
0 references
oracle
0 references