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
1987
0 references
nondeterministic Turing machines
0 references
counting class
0 references
relativizations
0 references
0 references
0.8965972
0 references
0.89389724
0 references
0.88448054
0 references
0 references
0.8482784
0 references
0.8375834
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