<p>There have been several such theorems proved over the years. More recently, there have been efforts to establish &quot;Rice-style&quot; theorems for problems on circuits. (It is natural to replace &quot;machines&quot; with &quot;circuits&quot;. Once you do that, the total number of possible inputs becomes fixed, so you do not run into undecidability issues.) Two references:</p>
<blockquote>
<p>Bernd Borchert, Frank Stephan: <a href="http://dx.doi.org/10.1002/1521-3870(200010)46:4%3C489::AID-MALQ489%3E3.0.CO;2-F" rel="noreferrer">Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory.</a> Math. Log. Q. 46(4): 489-504 (2000)</p>
<p>Lane A. Hemaspaandra, Jörg Rothe: <a href="http://dx.doi.org/10.1016/S0304-3975(98)00344-2" rel="noreferrer">A second step towards complexity-theoretic analogs of Rice's Theorem.</a> Theor. Comput. Sci. 244(1-2): 205-217 (2000)</p>
</blockquote>
<p>Here is an example result: &quot;Every nonempty proper counting property of circuits is UP-hard.&quot; 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).</p>
<p>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.</p>

CC BY-SA 2.5
2010-08-27T05:30:56.413Z
2010-08-27T15:15:06.957Z
2020-06-17T09:38:08.363Z
Ryan Williams
<p>A Rice-style theorem for $NP$ is the result proved by <a href="http://www.sciencedirect.com/science/article/pii/S0304397504001458" rel="noreferrer">Hemaspaandra and Thakur</a> which states that every nontrivial language property of $NP$ sets is $NP$-hard.</p>

CC BY-SA 3.0
2014-01-18T13:13:05.413Z
2014-01-18T13:13:05.413Z
Mohammad Al-Turkistany
<p>Proving such a complexity theoretic version of Rice's Theorem was a motivation for me to study program obfuscation.  </p>

<p>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.</p>

<p>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.  </p>

<p>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?</p>

<p>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.</p>

<p>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</p>

CC BY-SA 2.5
2010-08-29T02:57:06.133Z
2010-08-29T02:57:06.133Z
Russell Impagliazzo
<p>Rice's theorem states that every nontrivial property of the set recognized by some Turing machine is undecidable.</p>

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

CC BY-SA 2.5
2010-08-27T02:57:28.397Z
I'd ask you to clarify a bit more, but I think I know what you mean.  The answer is essentially that Rice's theorem still applies.  Although it's not the same question, I think your question is equally well answered by this: http://cstheory.stackexchange.com/questions/161/can-it-be-determined-if-language-l-lies-in-np/162#162.  Voting to close as duplicate.
Joshua Grochow
CC BY-SA 2.5
2010-08-27T03:14:16.133Z
My question is NOT about deciding weather a set is in NP, It is about finding a theorem that could tell which problems in NP are not efficiently computable (do not have polynomial time algorithm).
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-08-27T03:41:06.780Z
Joshua, I'm looking for theorem which states some conditions that can be used to prove the intractability of problems (non-existence of polynomial time algorithm).
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-08-27T05:32:24.960Z
What do you mean by a property being intractable? In order to talk about intractability of a property, we need the property to be algorithmically decidable. For an algorithm A to decide if a language L has some property, L must be given as some *finite* input to A.  The standard way to do that is to let $M_1, M_2, ...$ be an enumeration of clocked nondeterministic TMs capturing all languages in NP.  Then we want $A(i)=1$ if $L(M_i)$ has the property and $A(i)=0$ otherwise. Rice's Theorem applies.  If you have something else in mind, please clarify what.
Joshua Grochow
CC BY-SA 2.5
2010-08-27T05:33:40.213Z
It is too much to ask for something which can be used to "prove" an NP set is intractable to solve! But there are Rice-ish theorems which can be used to establish "NP-hardness" of problems.
Ryan Williams
CC BY-SA 2.5
2010-08-27T06:05:03.983Z
Joshua, let me use an example, the set of 3-colorable graphs is  in NP. I want a Rice-style theorem which can be used to prove that 3-coloring problem does not have any polynomial time algorithm (provably intractable)
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-08-27T06:28:49.230Z
turkistany:  you're asking for a proof that P!= NP? :)  Or do you mean the algorithm in restricted in some sense?
arnab
CC BY-SA 2.5
2010-08-27T15:08:08.510Z
arnab, Yes, the to-be discovered theorem would enable us to prove P!=NP
Mohammad Al-Turkistany
<cc.complexity-theory><computability><np>
Is there a complexity theory analogue of Rice's theorem in computability theory?
Mohammad Al-Turkistany
# Is there a complexity theory analogue of Rice's theorem in computability theory?

(Asked by: username_0 on 2010-08-27)

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.

**Tags:** cc.complexity-theory, computability, np

> **Comments:**
> **username_1**: I'd ask you to clarify a bit more, but I think I know what you mean.  The answer is essentially that Rice's theorem still applies.  Although it's not the same question, I think your question is equally well answered by this: http://cstheory.stackexchange.com/questions/161/can-it-be-determined-if-language-l-lies-in-np/162#162.  Voting to close as duplicate.  
> **username_0**: My question is NOT about deciding weather a set is in NP, It is about finding a theorem that could tell which problems in NP are not efficiently computable (do not have polynomial time algorithm).  
> **username_0**: Joshua, I'm looking for theorem which states some conditions that can be used to prove the intractability of problems (non-existence of polynomial time algorithm).  
> **username_1**: What do you mean by a property being intractable? In order to talk about intractability of a property, we need the property to be algorithmically decidable. For an algorithm A to decide if a language L has some property, L must be given as some *finite* input to A.  The standard way to do that is to let $M_1, M_2, ...$ be an enumeration of clocked nondeterministic TMs capturing all languages in NP.  Then we want $A(i)=1$ if $L(M_i)$ has the property and $A(i)=0$ otherwise. Rice's Theorem applies.  If you have something else in mind, please clarify what.  
> **username_2**: It is too much to ask for something which can be used to "prove" an NP set is intractable to solve! But there are Rice-ish theorems which can be used to establish "NP-hardness" of problems.  
> **username_0**: Joshua, let me use an example, the set of 3-colorable graphs is  in NP. I want a Rice-style theorem which can be used to prove that 3-coloring problem does not have any polynomial time algorithm (provably intractable)  
> **username_3**: turkistany:  you're asking for a proof that P!= NP? :)  Or do you mean the algorithm in restricted in some sense?  
> **username_0**: username_3, Yes, the to-be discovered theorem would enable us to prove P!=NP  

---

## 3 answers

### Answer by username_4 on 2010-08-29. Score: 39 | Accepted answer

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, username_4, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang: On the (Im)possibility of Obfuscating Programs. CRYPTO 2001:1-18


---

### Answer by username_2 on 2010-08-27. Score: 27

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.](http://dx.doi.org/10.1002/1521-3870(200010)46:4%3C489::AID-MALQ489%3E3.0.CO;2-F) 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.](http://dx.doi.org/10.1016/S0304-3975(98)00344-2) 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 by username_0 on 2014-01-18. Score: 6

A Rice-style theorem for $NP$ is the result proved by [Hemaspaandra and Thakur](http://www.sciencedirect.com/science/article/pii/S0304397504001458) which states that every nontrivial language property of $NP$ sets is $NP$-hard.


---

