Universal relations and {\#}P-completeness

DOI10.1016/j.tcs.2008.05.003zbMath1152.68018OpenAlexW2029591402MaRDI QIDQ954984

Guillaume Malod, Hervé Fournier

Publication date: 18 November 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.05.003

zbMATH Keywords

computational complexitycounting problems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Universal resolution for NP-complete problems
• Functions computable with nonadaptive queries to NP
• PP is as Hard as the Polynomial-Time Hierarchy
• The Complexity of Enumeration and Reliability Problems
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Universal relations and {\#}P-completeness