scientific article; zbMATH DE number 4041255

From MaRDI portal
Publication:3779736





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.











This page was built for publication:

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