Complexity of counting the optimal solutions
type: Item
instance of: scholarly article
title: Complexity of counting the optimal solutions
zbMATH Open document ID: 1171.68011
author: Miki Hermann
author: Reinhard Pichler
published in: Theoretical Computer Science
publication date: 2009-09-10T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5602742
zbMATH Keywords: computational complexity
zbMATH Keywords: counting complexity
zbMATH Keywords: optimization problems
MaRDI profile type: Publication
full work available at URL: j.tcs.2009.05.025
OpenAlex ID: W1980428853
cites work: The complexity of propositional closed world reasoning and circumscription
cites work: Complexity of generalized satisfiability counting problems
cites work: Subtractive reductions and complete problems for counting complexity classes
cites work: Q4298571
cites work: Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
cites work: Q4359457
cites work: Q4852904
cites work: Computing functions with parallel queries to NP
cites work: On counting and approximation
cites work: The complexity of optimization problems
cites work: Generalizations of Opt P to the polynomial hierarchy
cites work: The Complexity of Counting Functions with Easy Decision Version
cites work: Q3221403
cites work: The complexity of satisfiability problems
cites work: Positive Relativizations of Complexity Classes
cites work: The polynomial-time hierarchy
cites work: Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
cites work: Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
cites work: The complexity of computing the permanent
cites work: The Complexity of Enumeration and Reliability Problems
cites work: Bounded Query Classes
cites work: Complete sets and the polynomial-time hierarchy
DOI: 10.1016/J.TCS.2009.05.025
description: scientific article; zbMATH DE number 5602742