Subtractive reductions and complete problems for counting complexity classes

Arnaud Durand, Miki Hermann, Phokion G. Kolaitis

Type: Article

Publication Date: 2005-04-08

Citations: 53

DOI: https://doi.org/10.1016/j.tcs.2005.03.012

View Publication

Locations

Theoretical Computer Science - View

Similar Works

Action	Title	Year	Authors
+	#P-complete counting problems	2019	István Miklós
+	Subtractive Reductions and Complete Problems for Counting Complexity Classes	2000	Arnaud Durand Miki Hermann Phokion G. Kolaitis
+	Complexity dichotomies of counting problems	2012	Lizhen Ji Yat Sun Poon Lo Yang Shing‐Tung Yau
+	The complexity of counting problems	2001	Dominic Welsh Amy Gale
+	Rational transductions and complexity of counting problems	1995	Christian Choffrut Massimiliano Goldwurm
+	Counting Complexity	1997	Lance Fortnow
+ PDF Chat	Combinatorics of reductions between equivalence relations	2015	Dan Hathaway Sebastian Schneider
+	Holographic reduction for some counting problems	2011	Chen Yuan Haibin Kan
+	Computational Complexity Reductions Using Clifford Algebras	2010	René Schott G. Stacey Staples
+	p -projection reducibility and the complexity classes	1986	Ch Meinel
+	Complete problems and strong polynomial reducibilities	2005	K. Ganesan Steven Homer
+	Polynomial reducibilities and complete sets.	1977	Leonard Berman
+	Infinite sets of reductions	1987
+	Kolmogorov Complexity, Strong Reducibilities, and Computably Enumerable Sets	2000	Kejia Ho
+	On complexity of counting	2005	Marek Piotrów
+	Mapping the complexity of counting problems	2016	Heng Guo
+	Exotic Quantifiers, Complexity Classes, and Complete Problems	2007	Peter Bürgisser Felipe Cucker
+	Counting Problems	2003	Vijay V. Vazirani
+	A complexity theory for hard enumeration problems	2019	Nadia Creignou Markus Kröll Reinhard Pichler Sebastian Skritek Heribert Vollmer
+	Complexity problems in enumerative combinatorics	2018	Igor Pak

Works That Cite This (23)

Action	Title	Year	Authors
+ PDF Chat	Exploiting Treewidth for Projected Model Counting and Its Limits	2018	Johannes K. Fichte Markus Hecher Michael Morak Stefan Woltran
+ PDF Chat	Descriptive complexity of #P functions: A new perspective	2020	Arnaud Durand Anselm Haak Juha Kontinen Heribert Vollmer
+ PDF Chat	Parameterised Counting in Logspace	2023	Anselm Haak Arne Meier Om Prakash B. V. Raghavendra Rao
+	THE THOMPSON–HIGMAN MONOIDS M<sub>k,i</sub>: THE ${\mathcal J}$-ORDER, THE ${\mathcal D}$-RELATION, AND THEIR COMPLEXITY	2011	Jean-Camille Birget
+	The complexity of counting locally maximal satisfying assignments of Boolean CSPs	2016	Leslie Ann Goldberg Mark Jerrum
+ PDF Chat	Solving Projected Model Counting by Utilizing Treewidth and its Limits	2022	Johannes K. Fichte Markus Hecher Michael Morak Patrick Thier Stefan Woltran
+	The complexity of weighted counting for acyclic conjunctive queries	2013	Arnaud Durand Stefan Mengel
+	A structured view on weighted counting with relations to counting, quantum computation and applications	2020	Cassio P. de Campos Georgios Stamoulis Dennis Weyland
+	Complexity of counting the optimal solutions	2009	Miki Hermann Reinhard Pichler
+	Complexity of Counting the Optimal Solutions	2008	Miki Hermann Reinhard Pichler

Works Cited by This (4)

Action	Title	Year	Authors
+	The complexity of computing the permanent	1979	Leslie G. Valiant
+	The satanic notations	1995	Lane A. Hemaspaandra Heribert Vollmer
+	A complexity theory for feasible closure properties	1993	Mitsunori Ogiwara Lane A. Hemachandra
+	The Complexity of Enumeration and Reliability Problems	1979	Leslie G. Valiant