scientific article; zbMATH DE number 1759419

MaRDI QIDQ4536368zbMATH OpenFDO

Authors Arnaud Durand, Miki Hermann, Phokion G. Kolaitis

Publication date 4 November 2002

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Subtractive reductions and complete problems for counting complexity classes
• Gap-definable counting classes
• Complexity of generalized satisfiability counting problems
• The relative complexity of approximate counting problems
• scientific article; zbMATH DE number 58301

Cited in

(6)

• An inequality for polymatroid functions and its applications.
• Reducing the number of solutions of NP functions
• Incremental delay enumeration: space and time
• Subtractive reductions and complete problems for counting complexity classes
• Fine-Grained Reductions from Approximate Counting to Decision
• Picturing Counting Reductions with the ZH-Calculus

This page was built for publication:

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