A note on \(\#\mathcal P\)-completeness of NP-witnessing relations

DOI10.1016/j.ipl.2008.10.009zbMath1191.68341OpenAlexW1991202395MaRDI QIDQ976088

Noam Livne

Publication date: 16 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.10.009

zbMATH Keywords

computational complexityNP\(\#\mathcal P\)-completeness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

An efficient algorithm for polarizable interactions: a uniformly distributed one-dimensional case ⋮ Computing the probability of getting infected: on the counting complexity of bootstrap percolation

Cites Work

• The complexity of computing the permanent
• The complexity of optimization problems
• Unnamed Item
• Unnamed Item

This page was built for publication: A note on \(\#\mathcal P\)-completeness of NP-witnessing relations