Looking for an analogue of Rice's theorem in circuit complexity theory (Q4364508)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1088195
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Looking for an analogue of Rice's theorem in circuit complexity theory |
scientific article; zbMATH DE number 1088195 |
Statements
13 August 1998
0 references
Rice's theorem
0 references
Boolean circuits
0 references
Boolean functions
0 references
absolute counting problems
0 references
gap counting problems
0 references
relative counting problems
0 references
UP-hard problems
0 references
0.9157178997993468
0 references
0.8685813546180725
0 references
0.8512954711914062
0 references
Looking for an analogue of Rice's theorem in circuit complexity theory (English)
0 references
The paper under review is motivated by the search for an analogue of Rice's theorem in complexity theory. An approach the authors chose is that of Boolean functions. They begin by observing that the following, most `natural', analogue of Rice's theorem is wrong (assuming P \(\neq\) NP): Let \(A\) be a nonempty proper subset of the set of all Boolean functions. Then the following problem is NP-hard: Given a circuit \(c\), does it compute a function from \(A\)? In view of this observation, one has to satisfy oneself with more restrictive and less intuitive Rice-style theorems. Of them, the present note contains several, each of which deals with problems from one of the three categories: the so-called absolute counting problems, gap counting problems, and relative counting problems. The general structure of every Rice-style theorem is this: any nontrivial \{absolute, gap, relative\} counting property of Boolean circuits is UP-hard with respect to polynomial time Turing reductions. Some applications to randomized computations are deduced, and open problems discussed. For the entire collection see [Zbl 0870.00023].
0 references