A second step towards complexity-theoretic analogs of Rice's Theorem
✍ Scribed by Lane A. Hemaspaandra; Jörg Rothe
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 122 KB
- Volume
- 244
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
Rice's Theorem states that every nontrivial language property of the recursively enumerable sets is undecidable. Borchert and Stephan (1997) 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 SPPhardness. 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-inÿnite counting property of circuits is SPP-hard. We also raise their general lower bound from unambiguous nondeterminism to constant-ambiguity nondeterminism.