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

&
Mathematical Logic Quarterly 46 (4):489-504 (2000)
  Copy   BIBTEX

Abstract

Rice's Theorem says that every nontrivia semantic property of programs is undecidable. In this spirit we show the following: Every nontrivia absolute 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

Categories

Add categories

Keywords

Reprint years

DOI

10.1002/1521-3870(200010)46:4

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,202

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

The Chang-Łoś-Suszko theorem in a topological setting.Paul Bankston - 2006 - Archive for Mathematical Logic 45 (1):97-112.
On the Degrees of Diagonal Sets and the Failure of the Analogue of a Theorem of Martin.Keng Meng Ng - 2009 - Notre Dame Journal of Formal Logic 50 (4):469-493.
Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons.Dietmar Schuchardt & Hans-Dietrich Hecker - 1995 - Mathematical Logic Quarterly 41 (2):261-267.
Generic Complexity of Undecidable Problems.Alexei G. Myasnikov & Alexander N. Rybalov - 2008 - Journal of Symbolic Logic 73 (2):656 - 673.
Some Ramsey theory in Boolean algebra for complexity classes.Gregory L. McColm - 1992 - Mathematical Logic Quarterly 38 (1):293-298.
Rice and Rice-Shapiro Theorems for transfinite correction grammars.John Case & Sanjay Jain - 2011 - Mathematical Logic Quarterly 57 (5):504-516.
On Hide's magnetic analogue of Ertel's vorticity theorem.Wilfried Schröder & Hans-Jürgen Treder - 1997 - Foundations of Physics 27 (10):1453-1455.
An analogue of the Baire category theorem.Philipp Hieronymi - 2013 - Journal of Symbolic Logic 78 (1):207-213.
A topological analog to the rice-Shapiro index theorem.Louise Hay & Douglas Miller - 1982 - Journal of Symbolic Logic 47 (4):824-832.
Agricultural Biotechnology and Environmental Justice.Kristen Hessler - 2011 - Environmental Ethics 33 (3):267-282.
On the complexity of the pancake problem.Fuxiang Yu - 2007 - Mathematical Logic Quarterly 53 (4):532-546.
Interest driven suppositional reasoning.John Pollock - manuscript
On interpreting Chaitin's incompleteness theorem.Panu Raatikainen - 1998 - Journal of Philosophical Logic 27 (6):569-586.
Edgar Morin's paradigm of complexity and gödel's incompleteness theorem.Yi-Zhuang Chen - 2004 - World Futures 60 (5 & 6):421 – 431.
The Surprise Examination Paradox and the Second Incompleteness Theorem.Shira Kritchman & Ran Raz - unknown

Analytics

Added to PP
2013-12-01

Downloads
8 (#1,243,760)

6 months
1 (#1,444,594)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references