A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem
<|reference_start|>A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem: Rice's Theorem states that every nontrivial language property of the recursively enumerable sets is undecidable. Borchert and Stephan initiated the search for complexity-theoretic analogs of Rice's Theorem. In particular, they proved that every nontrivial counting property of circuits is UP-hard, and that a number of closely related problems are SPP-hard.   The present paper studies whether their UP-hardness result itself can be improved to SPP-hardness. We show that their UP-hardness result 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. We also raise their general lower bound from unambiguous nondeterminism to constant-ambiguity nondeterminism.<|reference_end|>
@article{hemaspaandra1999a,
    title={A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem},
    author={Lane A. Hemaspaandra and Joerg Rothe},
    journal={arXiv preprint arXiv:cs/9907038},
    year={1999},
    number={earlier version appeared as University of Rochester TR-97-662},
    archivePrefix={arXiv},
    eprint={cs/9907038},
    primaryClass={cs.CC}
}