Is there a complexity theory analogue of Rice's theorem in computability theory?

Question

Rice's theorem states that every nontrivial property of the set recognized by some Turing machine is undecidable.

I am looking for complexity-theoretic Rice-type theorem that tells us which nontrivial properties of NP sets are intractable.

Answer 1

Proving such a complexity theoretic version of Rice's Theorem was a motivation for me to study program obfuscation.

Rice's theorem says in essence, that it is hard to understand the functions that programs compute, given the program. However, the reason these problems are undecideable is that they are infinitary. Even on one input, a program may never halt, and we need to consider what the program does on infinitely many inputs.

A finitary version of Rice's theorem would fix the input size and running time of a program, and say that the program is hard to understand. Once you've fixed these, you might as well view the program as a Boolean circuit. What properties of the function computed by a Boolean circuit are hard to compute? One example is ``not always 0'', which is the NP-complete Satisfiability problems. But unlike Rice's Theorem, there are some properties that are non-trivial but easy, even without understanding the circuit. We can always know that: the function computed by a circuit has a bounded circuit complexity (the size of the circuit). Also, we can always evaluate the circuit on inputs of our choice.

So say a property of $f_C$ is easy with Black-box access if it can be compute,d in probabilistic polynomial time by an algorithm that gets as input $n$, a bound on $|C|$ and oracle access to $f_C$. For example, satisfiability is not easy with black-box access, because we could imagine a circuit of size $n$ that only produces answer 1 on a randomly chosen input $x$. No black box algorithm could distinguish such a circuit from one that always returned 0, since the probability of querying the oracle on $x$ is exponentially small. On the other hand, the property $f(0..0)=1$ is black-box easy. The question is: are there any properties of $f_C$ that are decideable in probabilistic polynomial-time that are not easy with Black-box access?

While this question is open as far as I know, our intended approach was ruled out. We had hoped to prove this by showing that cryptographically secure program obfuscation was possible. However, Boaz proved the opposite: that it was impossible. This implicitly shows that black-box access to circuits is more limited than full access to the circuit description, but the proof is non-constructive, so I can't name any property as above that is easy given the circuit description but not with black-box access. It is interesting (at least to me) if such a property could be reverse engineered from our paper.

Here is the reference:Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang: On the (Im)possibility of Obfuscating Programs. CRYPTO 2001:1-18

Answer 2

There have been several such theorems proved over the years. More recently, there have been efforts to establish "Rice-style" theorems for problems on circuits. (It is natural to replace "machines" with "circuits". Once you do that, the total number of possible inputs becomes fixed, so you do not run into undecidability issues.) Two references:

Bernd Borchert, Frank Stephan: Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory. Math. Log. Q. 46(4): 489-504 (2000)

Lane A. Hemaspaandra, Jörg Rothe: A second step towards complexity-theoretic analogs of Rice's Theorem. Theor. Comput. Sci. 244(1-2): 205-217 (2000)

Here is an example result: "Every nonempty proper counting property of circuits is UP-hard." You can read the papers for definitions, but this roughly means that any property depending on the number of satisfying assignments to a circuit is hard for the class UP (hence intractable).

There is also older work on complexity-theoretic versions of Rice's theorem, in a different vein. I'm not familiar with it, but the above papers do cite them.

Answer 3

A Rice-style theorem for $NP$ is the result proved by Hemaspaandra and Thakur which states that every nontrivial language property of $NP$ sets is $NP$-hard.