scientific article; zbMATH DE number 4041255
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.
- Acceptor-definable counting classes
- Complexity classes with finite acceptance types
- Classes of bounded counting type and their inclusion relations
- Counting partial types in simple theories
- A Finite First-Order Theory of Classes
- Classification in finite model theory: counting finite algebras
- scientific article; zbMATH DE number 3987268
- Finite type invariants
- Implicit recursion-theoretic characterizations of counting classes
- scientific article; zbMATH DE number 5066581
- The chain method to separate counting classes
- A second step towards complexity-theoretic analogs of Rice's Theorem
- A reducibility for the dot-depth hierarchy
- Exact computation of the number of accepting paths of an NTM
- Relativized counting classes: Relations among thresholds, parity, and mods
- Hierarchies and reducibilities on regular languages related to modulo counting
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- Simultaneous strong separations of probabilistic and unambiguous complexity classes
- The inherent dimension of bounded counting classes
- Complexity classes defined by counting quantifiers
- Acceptor-definable counting classes
- Semantical counting circuits
- Classes of bounded counting type and their inclusion relations
- Generalized regular counting classes
- Complexity classes with finite acceptance types
- On the power of parity polynomial time
- Locally definable acceptance types for polynomial time machines
- On the power of parity polynomial time
- On the acceptance power of regular languages
- On the limiting proportion of types
- Probabilistic polynomial time is closed under parity reductions
- On the complexity of counting in the polynomial hierarchy
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)