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

DOI10.1016/J.IPL.2008.10.009MaRDI QIDQ976088zbMATH OpenOpenAlexFDO

Authors 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

\(\#\mathcal P\)-completenesscomputational complexityNP

Mathematics Subject Classification ID

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

Recommendations

• Universal relations and {\#}P-completeness
• Universal Relations and #P-Completeness
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
• scientific article; zbMATH DE number 4047100

Cites work

• scientific article; zbMATH DE number 3569828 (Why is no real title available?)
• scientific article; zbMATH DE number 1048042 (Why is no real title available?)
• The complexity of computing the permanent
• The complexity of optimization problems

Cited in

(4)

• 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
• Universal Relations and #P-Completeness
• Universal relations and {\#}P-completeness

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976088)