No label defined (Q3779736)

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

      Statements

      0 references
      0 references
      1987
      0 references
      nondeterministic Turing machines
      0 references
      counting class
      0 references
      relativizations
      0 references
      Counting classes are defined as follows. Consider nondeterministic Turing machines (NTM) having \(k+1\) distinguished final states 0,1,...,k and having a polynomial clock. An input x on an NTM M determines a vector \(n_ M(x)=(n_ 1,...,n_ k)\) where \(n_ i\) is the number of paths leading to the final state i. Let \(A\subseteq {\mathbb{N}}^ k \)be some fixed set. We call it acceptance type. M accepts x in the sense of A if and only if \(n_ M(x)\in A\). In an obvious way the counting class AP is defined containing all languages accepted in the sense of A by some polynomially clocked NTM. The paper studies all polynomial time classes defined by finite \(A\subseteq {\mathbb{N}}\). They form a rich hierarchy (which is proper only if \(P\neq NP)\). Several techniques must be developed to separate these classes under relativizations. All reasonable separation and collapse results under relativization are proved to be possible.
      0 references

      Identifiers