A second step towards complexity-theoret
β
Lane A. Hemaspaandra; JΓΆrg Rothe
π
Article
π
2000
π
Elsevier Science
π
English
β 122 KB
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-h