A second step towards complexity-theoretic analogs of Rice's Theorem

Rice's Theorem states that every nontrivial language property of the recurs ively enumerable sets is undecidable. Borchert and Stephan (1997) initiated the search for complexity-theoretic analogs of Rice's Theorem. In particul ar, they proved that every nontrivial counting property of circuits is W-ha rd, and that a number of closely related problems are SPP-hard. The present paper studies whether their UP-hardness result itself can be im proved to SPP-hardness. We show that their UP-hardness result cannot be str engthened to SPP-hardness unless unlikely complexity class containments hol d. Nonetheless, we prove that every P-constructibly bi-infinite counting pr operty of circuits is SPP-hard. We also raise their general lower bound fro m unambiguous nondeterminism to constant-ambiguity nondeterminism. (C) 2000 Elsevier Science B.V. All rights reserved.