14
$\begingroup$

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 ?

Improve this question
$\endgroup$
3
  • $\begingroup$ I have edited the question to try to make it easier to read. Apologies if I have altered your intention. $\endgroup$
    – András Salamon
    Commented May 14, 2011 at 13:03
  • $\begingroup$ @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. $\endgroup$
    – Ludovic Patey
    Commented May 14, 2011 at 13:11
  • $\begingroup$ Some related posts: proofs, barriers, and P vs NP, do the proofs that permanent is not in uniform $TC^0$ relativize?, which results in complexity theory make essential use of uniformity? $\endgroup$
    – Kaveh
    Commented May 16, 2011 at 9:08

4 Answers 4

Reset to default
18
$\begingroup$

Depends on how you formalize diagonalization. Kozen has a paper that shows any complexity class separation must be a diagonalization proof.

Improve this answer
$\endgroup$
1
  • $\begingroup$ +1 I think I read this in your blog and I was waiting for your answer :) $\endgroup$
    – Mohammad Al-Turkistany
    Commented May 15, 2011 at 21:37
6
$\begingroup$

To add to Fortnow's answer, continuing Kozen's work, Nash, Impagliazzo, and Remmel 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.

Improve this answer
$\endgroup$
5
$\begingroup$

Since diagonalization relativizes, any complexity result implying contradictory relativizations cannot be based on diagonalization. Quoting Arora-Barak:

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). A recent breakthrough in class separations based on proving circuit lower bounds is discussed in [1] and [2].

Another major technique which does not relativize is arithmetization. The technique was first used to prove that $P^{PH} \subseteq IP$ (Lund et al.), and later to prove IP = PSPACE. This technique was proved to be insufficient to resolve P vs NP by Aaronson and Wigderson (termed algebrization barrier).

Improve this answer
$\endgroup$
8
  • 2
    $\begingroup$ 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". $\endgroup$
    – András Salamon
    Commented May 14, 2011 at 15:09
  • $\begingroup$ @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. $\endgroup$
    – Ludovic Patey
    Commented May 14, 2011 at 15:25
  • $\begingroup$ 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? $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Commented May 14, 2011 at 16:23
  • 1
    $\begingroup$ @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. cseweb.ucsd.edu/~russell/ias.ps $\endgroup$
    – András Salamon
    Commented May 14, 2011 at 22:47
  • 1
    $\begingroup$ There is some debate about this: see for instance Fortnow's response to the AIV paper: people.cs.uchicago.edu/~fortnow/papers/relative.pdf $\endgroup$
    – Suresh Venkat
    Commented May 15, 2011 at 2:58
5
$\begingroup$

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.)
Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Kaveh
    Commented May 18, 2011 at 4:47
  • $\begingroup$ 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". $\endgroup$
    – Kaveh
    Commented May 18, 2011 at 4:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.