Lower bounds and the hardness of counting properties

DOI10.1016/J.TCS.2004.03.004zbMATH Open1105.68048OpenAlexW2004627063MaRDI QIDQ703531FDOQ703531

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

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

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)

Cites Work

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

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)