Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR96-060 | 19th November 1996 00:00

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

RSS-Feed




TR96-060
Authors: Bernd Borchert, Frank Stephan
Publication: 26th November 1996 18:25
Downloads: 970
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint