✦ LIBER ✦

Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory

✍ Scribed by Bernd Borchert; Frank Stephan

Publisher: John Wiley and Sons
Year: 2000
Tongue: English
Weight: 223 KB
Volume: 46
Category: Article
ISSN: 0044-3050
DOI: 10.1002/1521-3870(200010)46:4<489::aid-malq489>3.0.co;2-f

No coin nor oath required. For personal study only.

✦ Synopsis

Rice's Theorem says that every nontrivial semantic property of programs is undecidable. In this spirit we show the following: Every nontrivial absolute (gap, relative) counting property of circuits is UP-hard with respect to polynomial-time Turing reductions.

For generators [31] we show a perfect analogue of Rice's Theorem.