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 the normal view instead:

scientific article; zbMATH DE number 683608
Language Label Description Also known as
default for all languages
No label defined
    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
      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
      0 references
      0 references
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references