A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem
| dc.creator | Hemaspaandra, Lane A. | |
| dc.creator | Rothe, Joerg | |
| dc.date | 1999-07-25 | |
| dc.date.accessioned | 2026-07-07T03:24:16Z | |
| dc.date.available | 2026-07-07T03:24:16Z | |
| dc.description | 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. | |
| dc.description | 14 pages. To appear in Theoretical Computer Science | |
| dc.identifier | https://arxiv.org/abs/cs/9907038 | |
| dc.identifier | http://arxiv.org/abs/cs/9907038 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/33260 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.1.3 | |
| dc.title | A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem | |
| dc.type | text |