Universal Relations and #P-Completeness

DOI10.1007/11758471_35zbMATH Open1183.68299OpenAlexW1586230313MaRDI QIDQ3434571FDOQ3434571

Authors: Hervé Fournier, Guillaume Malod 

Publication date: 2 May 2007

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11758471_35

Recommendations

• Universal relations and {\#}P-completeness
• A note on \(\#\mathcal P\)-completeness of NP-witnessing relations
• #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
• Relativizations of the P =? NP and Other Problems: Developments in Structural Complexity Theory
• Universal resolution for NP-complete 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)

Cited In (8)

• Universal relations and {\#}P-completeness
• #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
• A note on \(\#\mathcal P\)-completeness of NP-witnessing relations
• A domain theoretic characterisation of the universal relation
• On the spectra of universal relational sentences
• Universal computably enumerable equivalence relations
• Title not available (Why is that?)
• Compact universal relation in varieties with constants

This page was built for publication: Universal Relations and #P-Completeness

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