Skip to main content
added 10 characters in body
Source Link
Kaveh
  • 21.8k
  • 8
  • 84
  • 185

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 byfor other problems that we want to apply the method to applythem.
  4. YouWe can turn the separation arguments tointo "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.)

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 by other problems that we want the method to apply.
  4. You can turn the separation arguments to "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.)

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.)
added 298 characters in body; added 18 characters in body
Source Link
Kaveh
  • 21.8k
  • 8
  • 84
  • 185

Are there class separation proofs not based on diagonalization?

Yes, there are, but not for uniform complexity classes (AFAIK). 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 non-uniformnonuniform complexity class separationseparations can be turned into "self reference" since-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". ThereAFAIK, there is not any consensus on the answers whento the question "when two proofs are identical in essence (AFAIK)?".

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 most 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 by other problems that we want the method to apply. 
  4. You can turn the separation arguments to "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? YouWe need a proof! And the paper (AFAIU) doesn't give youus any idea on how to come up with those proofs. If youwe have ana separation argument youwe 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.)

Are there class separation proofs not based on diagonalization?

Yes, there are, but not for uniform complexity classes (AFAIK).

Can we find a self-reference mechanism behind them?

I don't think the non-uniform complexity class separation can be turned into "self reference" since they are not uniform and cannot be enumerated.

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

Depends on what you mean by "canonical". There is not any consensus on the answers when two proofs are identical in essence (AFAIK).

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).
  3. the most 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 by other problems that we want the method to apply. You can turn the separation arguments to "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? You need a proof! And the paper (AFAIU) doesn't give you any idea on how to come up with those proofs. If you have an separation argument you 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.)

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 by other problems that we want the method to apply. 
  4. You can turn the separation arguments to "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.)
Source Link
Kaveh
  • 21.8k
  • 8
  • 84
  • 185

Are there class separation proofs not based on diagonalization?

Yes, there are, but not for uniform complexity classes (AFAIK).

Can we find a self-reference mechanism behind them?

I don't think the non-uniform complexity class separation can be turned into "self reference" since they are not uniform and cannot be enumerated.

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

Depends on what you mean by "canonical". There is not any consensus on the answers when two proofs are identical in essence (AFAIK).

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).
  3. the most 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 by other problems that we want the method to apply. You can turn the separation arguments to "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? You need a proof! And the paper (AFAIU) doesn't give you any idea on how to come up with those proofs. If you have an separation argument you 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.)