EuDML | Browse

Displaying 21 – 24 of 24

On the parameterized complexity of approximate counting

J. Andrés Montoya (2011)

RAIRO - Theoretical Informatics and Applications

In this paper we study the parameterized complexity of approximating the parameterized counting problems contained in the class $# W [P]$ , the parameterized analogue of $# P$ . We prove a parameterized analogue of a famous theorem of Stockmeyer claiming that approximate counting belongs to the second level of the polynomial hierarchy.

On the robustness of ALMOST- $ℛ$

Ronald V. Book, Elvira Mayordomo (1996)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

On the structure of Valiant's complexity class.

Bürgisser, Peter (1999)

Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]

On the syntactic complexity of tree series

Symeon Bozapalidis, Antonios Kalampakas (2010)

RAIRO - Theoretical Informatics and Applications

We display a complexity notion based on the syntax of a tree series which yields two distinct hierarchies, one within the class of recognizable tree series and another one in the class of non-recognizable tree series.

Displaying 21 – 24 of 24

On the parameterized complexity of approximate counting

On the robustness of ALMOST- ℛ

On the structure of Valiant's complexity class.

On the syntactic complexity of tree series

Currently displaying 21 – 24 of 24

On the robustness of ALMOST- $ℛ$