Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory
Bernd Borchert, Frank Stephan · Mathematical logic quarterly · 2000
Rice's Theorem says that every nontrivia semantic property of programs is undecidable. In this spirit we show the following: Every nontrivia absolute (gap, relative) counting property of circuits is UP-hard with respect to polynomial-time Turing reductions. For generators [31] we show a perfect analogue of Rice's Theorem.