A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem

Details A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem

1999-07-25

arxiv.org/abs/cs/9907038v1

Computer Science

Computational Complexity

14 pages. To appear in Theoretical Computer Science

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-619306