|
|||||
|
|
Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory |
|
| Authors: | Bernd Borchert Frank Stephan |
| Abstract: | 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. |
| Keywords: | Rice's Theorem Counting problems Promise classes UP‐hard NP‐hard generators |