Lower bounds and the hardness of counting properties

DOI10.1016/j.tcs.2004.03.004zbMath1105.68048OpenAlexW2004627063MaRDI QIDQ703531

Mayur Thakur, Hemaspaandra, Lane A.

Publication date: 11 January 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.03.004

zbMATH Keywords

NPLower boundsCircuitsCounting propertiesLanguage propertiesRelativizationRice's TheoremUP

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Does Looking Inside a Circuit Help

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the construction of parallel computers from various basis of Boolean functions
• NP is as easy as detecting unique solutions
• The complexity of combinatorial problems with succinct input representation
• Turing machines with few accepting computations and low sets for PP
• A uniform approach to define complexity classes
• A comparison of polynomial time reducibilities
• Relative complexity of checking and evaluating
• Gap-definable counting classes
• A second step towards complexity-theoretic analogs of Rice's Theorem
• A complexity theory for feasible closure properties
• On completely recursively enumerable classes and their key arrays
• On the unique satisfiability problem
• The Boolean Hierarchy II: Applications
• The Complexity of Enumeration and Reliability Problems
• On the Complexity of Flowchart and Loop Program Schemes and Programming Languages
• Complexity classes defined by counting quantifiers
• Threshold Computation and Cryptographic Security
• Restrictive Acceptance Suffices for Equivalence Problems
• Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory
• P-Printable Sets
• On the power of parity polynomial time
• Classes of Recursively Enumerable Sets and Their Decision Problems
• The complexity theory companion

This page was built for publication: Lower bounds and the hardness of counting properties