Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory

DOI<489::AID-MALQ489>3.0.CO;2-F 10.1002/1521-3870(200010)46:4<489::AID-MALQ489>3.0.CO;2-FzbMath0964.03039OpenAlexW2024071675MaRDI QIDQ4521124

Bernd Borchert, Frank Stephan

Publication date: 16 July 2001

Full work available at URL: https://doi.org/10.1002/1521-3870(200010)46:4<489::aid-malq489>3.0.co;2-f

zbMATH Keywords

generatorsNP-hardRice's theorempromise classescounting property of circuitspolynomial-time Turing reductionsUP-hard

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Lower bounds and the hardness of counting properties ⋮ Does Looking Inside a Circuit Help

This page was built for publication: Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory