ECCC-Report TR96-060https://eccc.weizmann.ac.il/report/1996/060Comments and Revisions published for TR96-060en-usTue, 26 Nov 1996 18:25:02 +0200
Paper TR96-060
| Looking for an Analogue of Rice's Theorem in Complexity Theory |
Bernd Borchert,
Frank Stephan
https://eccc.weizmann.ac.il/report/1996/060 Rice's Theorem says that every nontrivial semantic property
of programs is undecidable. It 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.
Tue, 26 Nov 1996 18:25:02 +0200https://eccc.weizmann.ac.il/report/1996/060