Lower Bounds and the Hardness of Counting Properties
Lane A. Hemaspaandra, Mayur Thakur · 2002
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. Hemaspaandra and Rothe [HR00] improved the UP-hardness lower bound to UP O (1)-hardness. The present paper raises the lower bound for nontrivial counting properties from UP O (l)-hardness to FewPhardness, i.e., from constant-ambiguity nondeterminism to polynomial-ambiguity nondeterminism. Furthermore, we prove that this lower bound is rather tight with respect to relativizable techniques, i.e., no relativizable technique can raise this lower bound to FewP-≤ 1-tt -hardness. We also prove a Rice-style theorem for NP, namely that every nontrivial language property of NP sets is NP-hard.