Rice-Style Theorems for Complexity Theory
Lane A. Hemaspaandra, Mamta Thakur · 2001
Rice's Theorem states that all nontrivial language properties of recursively enumerable sets are undecidable. Borchert and Stephan [BS00] started the search for complexity-theoretic analogs of Rice's Theorem, and proved that every nontrivial counting property of boolean circuits is UP-hard.