<p>To add to Fortnow's answer, continuing Kozen's work, <a href="http://www.computer.org/portal/web/csdl/abs/proceedings/complexity/2003/1879/00/18790337abs.htm" rel="noreferrer">Nash, Impagliazzo, and Remmel</a> formalized a notion of strong diagonalization and gave some evidence that it does not relativize. To partially answer your first question, their results show that some class separation proofs can not be based on strong diagonalization. Here is the abstract:</p>
<blockquote>
<p>We define and study strong diagonalization and compare it to weak diagonalization, implicit in [7]. Kozen's result in [7] shows that virtually every separation can be recast as weak diagonalization. We show that there are classes of languages which can not be separated by strong diagonalization and provide evidence that strong diagonalization does not relativize. We also define two kinds of indirect diagonalization and study their power.</p>
<p>Since we define strong diagonalization in terms of universal languages, we study their complexity. We distinguish and compare weak and strict universal languages. Finally we analyze some apparently weaker variants of universal languages, which we call pseudouniversal languages, and show that under weak closure conditions they easily yield universal languages.</p>
</blockquote>
<p>1-Nash, A., Impagliazzo, R., Remmel; J. &quot;Universal Languages and the Power of
Diagonalization.&quot; 18th Annual IEEE Conference on Computational Complexity
(CCC'03), p. 337, 2003.</p>

CC BY-SA 3.0
2011-05-15T23:21:10.530Z
2011-05-15T23:28:12.893Z
2020-06-17T09:38:08.363Z
Mohammad Al-Turkistany
<blockquote>
  <p>Are there class separation proofs not based on diagonalization?</p>
</blockquote>

<p>Yes, there are, but not for uniform complexity classes. We don't have an argument to rule out such proofs but so far all separations between uniform complexity classes seem to use diagonalization at some place.</p>

<blockquote>
  <p>Can we find a self-reference mechanism behind them?</p>
</blockquote>

<p>I don't think the nonuniform complexity class separations can be turned into "self-reference" arguments because they are not uniform classes and cannot be enumerated, and for a self-reference argument we need to enumerate the members of the class.</p>

<blockquote>
  <p>does every class separation have a "canonical natural" proof (in an informal sense)?</p>
</blockquote>

<p>Depends on what you mean by "canonical". AFAIK, there is not any consensus on the answers to the question "when two proofs are identical in essence?".</p>

<blockquote>
  <p>If so, we should try to find non-relativizing arguments, rather than other proof schemes for open questions.
  Can every non-diagonal proof be rewritten into a diagonal one ?</p>
</blockquote>

<p>As others have pointed out, the answer depends on what you mean by a diagonalization. In the more general sense (Kozen's paper linked by Lance), the answer is yes for any two different "complexity classes" (as defined in Kozen's paper). You can turn the argument into a "diagonalization" argument. But:</p>

<ol>
<li>this does not apply to complexity classes which does not satisfy the requirements stated in Kozen's paper (i.e. are not Kozen "complexiy classes").</li>
<li>it is a <em>very</em> general kind of diagonalization. Kozen shows in the same paper that there are not "diagonalizations" which would satisfy some expected conditions for separating the classes like $P$ and $PSpace$. There are results by Lance Fornow and others (e.g. time-space trade off results) (including some of Ryan William's work) where diagonalization is used in an indirect way. This can be turned into direct "diagonalization" but it will not satisfy the nice properties that one might expect (like independence of counterexample for a set in the smaller class from the codes of the machines for that class, and it seems that is the reason they don't relativize). </li>
<li>the important thing is that <em>the more general a method is, the more limited its applications are</em> (if it is used by itself) because the method needs to work for more cases and this is a restriction on the method, we can not use the specific information we have about the problem if it is not shared or cannot be replaced by something similar for other problems that we want to apply the method to them. </li>
<li>We can turn the separation arguments into "diagonalization" arguments (considering the restriction I mentioned above), but the fact that "the diagonalizing function really separates the classes" itself needs a proof. Kozen's paper show that there <em>exists</em> a diagonalizing function if the classes are different, but how can we <em>know</em> that a given function is really diagonalizing? We need a proof! And the paper (AFAIU) doesn't give us any idea on how to come up with those proofs. If we have a separation argument we can turn it into a diagonalization proof, but that is only <em>after</em> having a proof. The original proof will serve as a part of the new diagonalization proof, it will show that the function is really diagonalizing. (And in a sense, the diagonalization proof constructed from Kozen's paper will not be "canonical" since it will be completely dependent on the original argument.)</li>
</ol>

CC BY-SA 3.0
2011-05-18T04:47:16.733Z
I should be more careful about your second question (Can we find a self-reference mechanism behind them?) and non-uniformity. I think you need to be more specific about what you mean by "a self-reference mechanism". The word "self-reference" is one of the words which is misused a lot (particularly in philosophical works), so we should be careful. The usual self-reference mechanism (in the sense of Godel, also see R. Smullyan's book "Diagonalization and Self-Reference", 1994) needs enumerating the objects (here TMs) of the smaller class in the language. But there are others that also use
Kaveh
CC BY-SA 3.0
2011-05-18T04:50:27.823Z
use the word "self-reference". E.g. K. Mulmuley uses it in his GCT's non-uniform setting in what he refers to as the "self-reference paradox". But it is difficult to see for me if that is what you have in mind when you are using "self-reference mechanism".
Kaveh
CC BY-SA 3.0
2011-05-16T09:41:09.473Z
2011-05-16T10:11:49.693Z
2011-05-16T10:11:49.693Z
Kaveh
<p>Since diagonalization relativizes, any complexity result implying contradictory relativizations cannot be based on diagonalization. Quoting <a href="http://www.cs.princeton.edu/theory/complexity/diagchap.pdf" rel="noreferrer">Arora-Barak</a>:</p>

<blockquote>
  <p>Results proven solely using diagonalization relativize in the sense that they hold also for TM’s with oracle access to $O$, for every oracle $O \subseteq \{0, 1\}^*$ . We can use this to show the limitations of such methods. In particular, relativizing methods alone cannot resolve the P vs. NP question.</p>
</blockquote>

<p>One major separation technique that does not relativize is proving circuit lower bounds. For instance, we know that all problems in $P$ have polynomial circuits. On the other hand, if we prove that an $NP$ problem has super-polynomial circuit (i.e. showing a super-polynomial lower bound), then $P\ne NP$. Unfortunately, Razborov and Rudich showed that this technique is unlikely to solve the P vs. NP problem. (See <a href="http://en.wikipedia.org/wiki/Natural_proof" rel="noreferrer">natural proof</a>). A recent breakthrough in class separations based on proving circuit lower bounds is discussed in 
<a href="http://lucatrevisan.wordpress.com/2010/11/08/a-circuit-lower-bound-breakthrough/" rel="noreferrer">[1]</a> and <a href="http://blog.computationalcomplexity.org/2010/11/breakthrough-circuit-lower-bound.html" rel="noreferrer">[2]</a>.</p>

<p>Another major technique which does not relativize is arithmetization. The technique was first used to prove that $P^{PH} \subseteq IP$ (<a href="http://portal.acm.org/citation.cfm?id=146605" rel="noreferrer">Lund <em>et al.</em></a>), and later to prove <a href="http://en.wikipedia.org/wiki/IP_%28complexity%29#Proof_that_IP_.3D_PSPACE" rel="noreferrer">IP = PSPACE</a>. This technique was proved to be insufficient to resolve P vs NP by <a href="http://portal.acm.org/citation.cfm?id=1374481" rel="noreferrer">Aaronson and Wigderson</a> (termed <em>algebrization barrier</em>).</p>

CC BY-SA 3.0
2011-05-14T15:09:28.920Z
Note that Baker, Gill, and Solovay did not say diagonalization _cannot_ work, but made a more nuanced statement "It seems unlikely that ordinary diagonalization methods are adequate".
András Salamon
CC BY-SA 3.0
2011-05-14T15:25:29.823Z
@Sadeq I don't agree that diagonalization relativizes. For example, you could define a diagonal machine based on a property taking in account computation locality property, which does not relativize.
Ludovic Patey
CC BY-SA 3.0
2011-05-14T16:23:39.943Z
Algebrization is not a technique, but rather a concept similar to relativization. I suppose you mean arithmetization instead. And what is the connection to natural proofs?
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2011-05-14T16:28:00.287Z
Regarding Natural Proofs. It was introduced by *Razborov* and Rudich. And they do of course not show that proving circuit lower bounds would not be a way to separate P and NP, but rather argue for the difficulty of using most known techniques for that purpose.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2011-05-14T17:25:12.977Z
@Kristoffer: Thanks for the points. I made the appropriate changes.  @András: Isn't that too conservative, given the Arora-Barak quote above? @Monoïd: Well, I'm not very familiar with "computation locality"; however, as Arora-Barak points out, if the proof solely depends on diagonalization, then it relativizes.
Sadeq Dousti
CC BY-SA 3.0
2011-05-14T22:47:12.070Z
@Sadeq: BGS were clearly allowing a more inclusive definition of diagonalization than Arora-Barak seem to intend.  If a set theorist like Robert Solovay thinks there might be other notions of diagonalization that do not relativize, then we should perhaps leave that possibility open.  Note page 75 of A&B does not dismiss the possibility that some kind of diagonalization uses a nonrelativizing fact about Turing machines; the still-unpublished Arora-Impagliazzo-Vazirani manuscript indicates that there are quite subtle issues involved.  http://cseweb.ucsd.edu/~russell/ias.ps
András Salamon
CC BY-SA 3.0
2011-05-15T02:58:24.953Z
There is some debate about this: see for instance Fortnow's response to the AIV paper: http://people.cs.uchicago.edu/~fortnow/papers/relative.pdf
Suresh Venkat
CC BY-SA 3.0
2011-05-15T06:20:57.087Z
@András, @Suresh: Thanks so much. I have to read those results...
Sadeq Dousti
CC BY-SA 3.0
2011-05-14T14:16:43.087Z
2011-05-14T17:34:40.283Z
2011-05-14T17:34:40.283Z
Sadeq Dousti
<p>Depends on how you formalize diagonalization. Kozen has a <a href="http://dx.doi.org/10.1016/0304-3975%2880%2990017-1">paper</a> that shows any complexity class separation must be a diagonalization proof. </p>

CC BY-SA 3.0
2011-05-15T21:37:26.340Z
+1 I think I read this in your blog and I was waiting for your answer :)
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-05-15T21:10:49.740Z
2011-05-15T21:10:49.740Z
Lance Fortnow
<p>I don't remember having seen a class separation not based on diagonalization and relativization results.  Diagonalization could still be used to separate remaining known classes, because non-relativizing arguments might still be used in the diagonalization conclusion, or in the diagonalized Turing machine construction.  Here are some related questions:</p>

<blockquote>
  <p>Are there class separation proofs not based on diagonalization?</p>
</blockquote>

<p>And if so</p>

<blockquote>
  <p>Can we find a self-reference mechanism behind them ?</p>
</blockquote>

<p>Further,</p>

<blockquote>
  <p>does every class separation have a "canonical natural" proof (in an informal sense)?</p>
</blockquote>

<p>If so, we should try to find non-relativizing arguments, rather than other proof schemes for open questions.</p>

<blockquote>
  <p>Can every non-diagonal proof be rewritten into a diagonal one ?</p>
</blockquote>

CC BY-SA 3.0
2011-05-14T13:03:33.580Z
I have edited the question to try to make it easier to read.  Apologies if I have altered your intention.
András Salamon
CC BY-SA 3.0
2011-05-14T13:11:02.543Z
@András Thank you for your edition. I'm often unclear. There is one alteration: I meant that diagonalization didn't fail because inside it, we can use non-relativizing arguments. I think relativisation and diagonalization are orthogonal. And I don't consider that it proofs which doesn't use diagonalization would use a deep self-reference mechanism, but only that in a deep understanding of the proof, we could discover an undeep self-reference mechanism ^^. I'll reedit those particular points.
Ludovic Patey
CC BY-SA 3.0
2011-05-16T09:08:35.497Z
Some related posts: [proofs, barriers, and P vs NP](http://cstheory.stackexchange.com/questions/1388/proofs-barriers-and-p-vs-np), [do the proofs that permanent is not in uniform $TC^0$ relativize?](http://cstheory.stackexchange.com/questions/1392/do-the-proofs-that-permanent-is-not-in-uniform-tc0-relativize/1437#1437), [which results in complexity theory make essential use of uniformity?](http://cstheory.stackexchange.com/questions/80/which-results-in-complexity-theory-make-essential-use-of-uniformity)
Kaveh
<cc.complexity-theory><complexity-classes><relativization><barriers>
Does diagonalization captures the essence of class separation ?
Ludovic Patey
# Does diagonalization captures the essence of class separation ?

(Asked by: username_0 on 2011-05-14)

I don't remember having seen a class separation not based on diagonalization and relativization results. Diagonalization could still be used to separate remaining known classes, because non-relativizing arguments might still be used in the diagonalization conclusion, or in the diagonalized Turing machine construction. Here are some related questions:

> Are there class separation proofs not based on diagonalization?

And if so

> Can we find a self-reference mechanism behind them ?

Further,

> does every class separation have a "canonical natural" proof (in an informal sense)?

If so, we should try to find non-relativizing arguments, rather than other proof schemes for open questions.

> Can every non-diagonal proof be rewritten into a diagonal one ?

**Tags:** cc.complexity-theory, complexity-classes, relativization, barriers
> **Comments:**
> **username_1**: I have edited the question to try to make it easier to read.  Apologies if I have altered your intention.  
> **username_0**: @András Thank you for your edition. I'm often unclear. There is one alteration: I meant that diagonalization didn't fail because inside it, we can use non-relativizing arguments. I think relativisation and diagonalization are orthogonal. And I don't consider that it proofs which doesn't use diagonalization would use a deep self-reference mechanism, but only that in a deep understanding of the proof, we could discover an undeep self-reference mechanism ^^. I'll reedit those particular points.  
> **username_2**: Some related posts: [proofs, barriers, and P vs NP](http://cstheory.stackexchange.com/questions/1388/proofs-barriers-and-p-vs-np), [do the proofs that permanent is not in uniform $TC^0$ relativize?](http://cstheory.stackexchange.com/questions/1392/do-the-proofs-that-permanent-is-not-in-uniform-tc0-relativize/1437#1437), [which results in complexity theory make essential use of uniformity?](http://cstheory.stackexchange.com/questions/80/which-results-in-complexity-theory-make-essential-use-of-uniformity)  

---

## 4 answers

### Answer by username_7 on 2011-05-15. Score: 18 | Accepted answer

Depends on how you formalize diagonalization. Kozen has a [paper](http://dx.doi.org/10.1016/0304-3975%2880%2990017-1) that shows any complexity class separation must be a diagonalization proof.

> **Comments:**
> **username_3**: +1 I think I read this in your blog and I was waiting for your answer :)  

---

### Answer by username_3 on 2011-05-15. Score: 6

To add to Fortnow's answer, continuing Kozen's work, [Nash, Impagliazzo, and Remmel](http://www.computer.org/portal/web/csdl/abs/proceedings/complexity/2003/1879/00/18790337abs.htm) formalized a notion of strong diagonalization and gave some evidence that it does not relativize. To partially answer your first question, their results show that some class separation proofs can not be based on strong diagonalization. Here is the abstract:

> We define and study strong diagonalization and compare it to weak diagonalization, implicit in [7]. Kozen's result in [7] shows that virtually every separation can be recast as weak diagonalization. We show that there are classes of languages which can not be separated by strong diagonalization and provide evidence that strong diagonalization does not relativize. We also define two kinds of indirect diagonalization and study their power.
>
> Since we define strong diagonalization in terms of universal languages, we study their complexity. We distinguish and compare weak and strict universal languages. Finally we analyze some apparently weaker variants of universal languages, which we call pseudouniversal languages, and show that under weak closure conditions they easily yield universal languages.

1-Nash, A., Impagliazzo, R., Remmel; J. "Universal Languages and the Power of
Diagonalization." 18th Annual IEEE Conference on Computational Complexity
(CCC'03), p. 337, 2003.


---

### Answer by username_2 on 2011-05-16. Score: 5

> Are there class separation proofs not based on diagonalization?

Yes, there are, but not for uniform complexity classes. We don't have an argument to rule out such proofs but so far all separations between uniform complexity classes seem to use diagonalization at some place.

> Can we find a self-reference mechanism behind them?

I don't think the nonuniform complexity class separations can be turned into "self-reference" arguments because they are not uniform classes and cannot be enumerated, and for a self-reference argument we need to enumerate the members of the class.

> does every class separation have a "canonical natural" proof (in an informal sense)?

Depends on what you mean by "canonical". AFAIK, there is not any consensus on the answers to the question "when two proofs are identical in essence?".

> If so, we should try to find non-relativizing arguments, rather than other proof schemes for open questions.
> Can every non-diagonal proof be rewritten into a diagonal one ?

As others have pointed out, the answer depends on what you mean by a diagonalization. In the more general sense (Kozen's paper linked by Lance), the answer is yes for any two different "complexity classes" (as defined in Kozen's paper). You can turn the argument into a "diagonalization" argument. But:

1. this does not apply to complexity classes which does not satisfy the requirements stated in Kozen's paper (i.e. are not Kozen "complexiy classes").
2. it is a *very* general kind of diagonalization. Kozen shows in the same paper that there are not "diagonalizations" which would satisfy some expected conditions for separating the classes like $P$ and $PSpace$. There are results by Lance Fornow and others (e.g. time-space trade off results) (including some of Ryan William's work) where diagonalization is used in an indirect way. This can be turned into direct "diagonalization" but it will not satisfy the nice properties that one might expect (like independence of counterexample for a set in the smaller class from the codes of the machines for that class, and it seems that is the reason they don't relativize).
3. the important thing is that *the more general a method is, the more limited its applications are* (if it is used by itself) because the method needs to work for more cases and this is a restriction on the method, we can not use the specific information we have about the problem if it is not shared or cannot be replaced by something similar for other problems that we want to apply the method to them.
4. We can turn the separation arguments into "diagonalization" arguments (considering the restriction I mentioned above), but the fact that "the diagonalizing function really separates the classes" itself needs a proof. Kozen's paper show that there *exists* a diagonalizing function if the classes are different, but how can we *know* that a given function is really diagonalizing? We need a proof! And the paper (AFAIU) doesn't give us any idea on how to come up with those proofs. If we have a separation argument we can turn it into a diagonalization proof, but that is only *after* having a proof. The original proof will serve as a part of the new diagonalization proof, it will show that the function is really diagonalizing. (And in a sense, the diagonalization proof constructed from Kozen's paper will not be "canonical" since it will be completely dependent on the original argument.)

> **Comments:**
> **username_2**: I should be more careful about your second question (Can we find a self-reference mechanism behind them?) and non-uniformity. I think you need to be more specific about what you mean by "a self-reference mechanism". The word "self-reference" is one of the words which is misused a lot (particularly in philosophical works), so we should be careful. The usual self-reference mechanism (in the sense of Godel, also see R. Smullyan's book "Diagonalization and Self-Reference", 1994) needs enumerating the objects (here TMs) of the smaller class in the language. But there are others that also use  
> **username_2**: use the word "self-reference". E.g. K. Mulmuley uses it in his GCT's non-uniform setting in what he refers to as the "self-reference paradox". But it is difficult to see for me if that is what you have in mind when you are using "self-reference mechanism".  

---

### Answer by username_4 on 2011-05-14. Score: 5

Since diagonalization relativizes, any complexity result implying contradictory relativizations cannot be based on diagonalization. Quoting [Arora-Barak](http://www.cs.princeton.edu/theory/complexity/diagchap.pdf):

> Results proven solely using diagonalization relativize in the sense that they hold also for TM’s with oracle access to $O$, for every oracle $O \subseteq \{0, 1\}^\*$ . We can use this to show the limitations of such methods. In particular, relativizing methods alone cannot resolve the P vs. NP question.

One major separation technique that does not relativize is proving circuit lower bounds. For instance, we know that all problems in $P$ have polynomial circuits. On the other hand, if we prove that an $NP$ problem has super-polynomial circuit (i.e. showing a super-polynomial lower bound), then $P\ne NP$. Unfortunately, Razborov and Rudich showed that this technique is unlikely to solve the P vs. NP problem. (See [natural proof](http://en.wikipedia.org/wiki/Natural_proof)). A recent breakthrough in class separations based on proving circuit lower bounds is discussed in
[[1]](http://lucatrevisan.wordpress.com/2010/11/08/a-circuit-lower-bound-breakthrough/) and [[2]](http://blog.computationalcomplexity.org/2010/11/breakthrough-circuit-lower-bound.html).

Another major technique which does not relativize is arithmetization. The technique was first used to prove that $P^{PH} \subseteq IP$ ([Lund *et al.*](http://portal.acm.org/citation.cfm?id=146605)), and later to prove [IP = PSPACE](http://en.wikipedia.org/wiki/IP_%28complexity%29#Proof_that_IP_.3D_PSPACE). This technique was proved to be insufficient to resolve P vs NP by [Aaronson and Wigderson](http://portal.acm.org/citation.cfm?id=1374481) (termed *algebrization barrier*).

> **Comments:**
> **username_1**: Note that Baker, Gill, and Solovay did not say diagonalization _cannot_ work, but made a more nuanced statement "It seems unlikely that ordinary diagonalization methods are adequate".  
> **username_0**: @Sadeq I don't agree that diagonalization relativizes. For example, you could define a diagonal machine based on a property taking in account computation locality property, which does not relativize.  
> **username_5**: Algebrization is not a technique, but rather a concept similar to relativization. I suppose you mean arithmetization instead. And what is the connection to natural proofs?  
> **username_5**: Regarding Natural Proofs. It was introduced by *Razborov* and Rudich. And they do of course not show that proving circuit lower bounds would not be a way to separate P and NP, but rather argue for the difficulty of using most known techniques for that purpose.  
> **username_4**: @Kristoffer: Thanks for the points. I made the appropriate changes.  @András: Isn't that too conservative, given the Arora-Barak quote above? @Monoïd: Well, I'm not very familiar with "computation locality"; however, as Arora-Barak points out, if the proof solely depends on diagonalization, then it relativizes.  
> **username_1**: @Sadeq: BGS were clearly allowing a more inclusive definition of diagonalization than Arora-Barak seem to intend.  If a set theorist like Robert Solovay thinks there might be other notions of diagonalization that do not relativize, then we should perhaps leave that possibility open.  Note page 75 of A&B does not dismiss the possibility that some kind of diagonalization uses a nonrelativizing fact about Turing machines; the still-unpublished Arora-Impagliazzo-Vazirani manuscript indicates that there are quite subtle issues involved.  http://cseweb.ucsd.edu/~russell/ias.ps  
> **username_6**: There is some debate about this: see for instance Fortnow's response to the AIV paper: http://people.cs.uchicago.edu/~fortnow/papers/relative.pdf  
> **username_4**: @András, @Suresh: Thanks so much. I have to read those results...  

---

