- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory
Mathematical Logic Quarterly 46 (4):489-504 (2000)
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 TheoremOther Versions
No versions found
My notes
Similar books and articles
The Ricean Objection: An Analogue of Rice's Theorem for First-order Theories.Igor Oliveira & Walter Carnielli - 2008 - Logic Journal of the IGPL 16 (6):585-590.
Erratum to “The Ricean Objection: An Analogue of Rice's Theorem for First-Order Theories” Logic Journal of the IGPL, 16: 585–590. [REVIEW]Igor Oliveira & Walter Carnielli - 2009 - Logic Journal of the IGPL 17 (6):803-804.
Gödel’s Incompleteness Phenomenon—Computationally.Saeed Salehi - 2014 - Philosophia Scientiae 18:23-37.
On computable numberings of families of Turing degrees.Marat Faizrahmanov - 2024 - Archive for Mathematical Logic 63 (5):609-622.
Mycielski among trees.Marcin Michalski, Robert Rałowski & Szymon Żeberski - 2021 - Mathematical Logic Quarterly 67 (3):271-281.
An extension of Shelah’s trichotomy theorem.Shehzad Ahmed - 2019 - Archive for Mathematical Logic 58 (1-2):137-153.
Analytics
Added to PP
2013-12-01
Downloads
15 (#1,220,934)
6 months
2 (#1,685,363)
2013-12-01
Downloads
15 (#1,220,934)
6 months
2 (#1,685,363)
Historical graph of downloads
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-667477cd97-sfdq8 dc2