Lower bounds and the hardness of counting properties

DOI10.1016/J.TCS.2004.03.004MaRDI QIDQ703531zbMATH OpenOpenAlexFDO

Authors Mayur Thakur, Lane A. Hemaspaandra

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

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

Recommendations

• A second step towards complexity-theoretic analogs of Rice's Theorem
• The intensional content of Rice's theorem
• scientific article; zbMATH DE number 1222577
• The Ricean Objection: An Analogue of Rice's Theorem for First-order Theories
• Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory

Cites work

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

Cited in

(2)

• Does looking inside a circuit help?
• Lower bounds for protrusion replacement by counting equivalence classes

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

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