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.
Is there a complexity theory analogue of Rice's theorem in computability theory?
cc.complexity theory;computability;np
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 whatthe 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 wellview 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-completeSatisfiability problems.    But unlike Rice's Theorem, there are some properties that arenon-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,din 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 arandomly 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 hadhoped 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 abovethat 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