Complexity-Theoretic Analogs of Rice''s Theorem
Lane A. Hemaspaandra, Jörg Rothe · UR Research (University of Rochester) · 1997
Rice's theorem states that every nontrivial language property of the recursively enumerable sets is undecidable. Borchert and Stephan initiated a search for complexity-theoretic analogs of Rice's Theorem. In particular, they proved that every nontrivial counting property of circuits is UP-hard. We extend their result by proving that every nontrivial counting property of circuits is UP_{O(1)}-hard; that is, we raise the lower bound from unambiguous nondeterminism to constant-ambiguity nondeterminism. We show that this conclusion cannot be strengthened to SPP-hardness unless unlikely complexity class containments hold. Nonetheless, we prove that every P-constructibly bi-infinite counting property of circuits is SPP-hard.