Looking for an analogue of Rice's theorem in circuit complexity theory

From MaRDI portal





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].











This page was built for publication: Looking for an analogue of Rice's theorem in circuit complexity theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4364508)