replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/

Source Link

edited Apr 13, 2017 at 12:32

1

This is a follow up to this question question, and is related to this question question of Shiva Kinali.

It seems that the proofs in these papers (Allender, Caussinus-McKenzie-Therien-Vollmer, Koiran-Perifel) use hierarchy theorems. I want to know if the proofs are "pure" diagonalization theorems, or if they use something more that usual diagonalization. So my question is

is there a reasonable relativization which puts permanent in uniform $\mathsf{TC^0}$?

Note that I am not sure how to define oracle access for uniform $\mathsf{TC^0}$, I know that finding the correct definition for small complexity classes is nontrivial. Another possibility is that permanent is not complete for $\mathsf{\#P}$ in the relativized universe, in which case I should use some complete problem for $\mathsf{\#P}$ in the relativized universe in place of it, and I think $\mathsf{\#P}$ should have a complete problem in any reasonable relativized universe.

This is a follow up to this question, and is related to this question of Shiva Kinali.

It seems that the proofs in these papers (Allender, Caussinus-McKenzie-Therien-Vollmer, Koiran-Perifel) use hierarchy theorems. I want to know if the proofs are "pure" diagonalization theorems, or if they use something more that usual diagonalization. So my question is

is there a reasonable relativization which puts permanent in uniform $\mathsf{TC^0}$?

Note that I am not sure how to define oracle access for uniform $\mathsf{TC^0}$, I know that finding the correct definition for small complexity classes is nontrivial. Another possibility is that permanent is not complete for $\mathsf{\#P}$ in the relativized universe, in which case I should use some complete problem for $\mathsf{\#P}$ in the relativized universe in place of it, and I think $\mathsf{\#P}$ should have a complete problem in any reasonable relativized universe.

This is a follow up to this question, and is related to this question of Shiva Kinali.

It seems that the proofs in these papers (Allender, Caussinus-McKenzie-Therien-Vollmer, Koiran-Perifel) use hierarchy theorems. I want to know if the proofs are "pure" diagonalization theorems, or if they use something more that usual diagonalization. So my question is

is there a reasonable relativization which puts permanent in uniform $\mathsf{TC^0}$?

Note that I am not sure how to define oracle access for uniform $\mathsf{TC^0}$, I know that finding the correct definition for small complexity classes is nontrivial. Another possibility is that permanent is not complete for $\mathsf{\#P}$ in the relativized universe, in which case I should use some complete problem for $\mathsf{\#P}$ in the relativized universe in place of it, and I think $\mathsf{\#P}$ should have a complete problem in any reasonable relativized universe.

Tweeted twitter.com/#!/StackCSTheory/status/301816658786402305

occurred Feb 13, 2013 at 22:14

fixing latex

Source Link

edit approved Jan 25, 2013 at 3:21

Community Bot

1

Do the proofs that permanent is not in uniform $TC^0$$\mathsf{TC^0}$ relativize?

This is a follow up to this question, and is related to this question of Shiva Kinali.

It seems that proofthe proofs in these papers (Allender, Caussinus-McKenzie-Therien-Vollmer, Koiran-Perifel) use hierarchy theorems. I want to know if the proofs are "pure" diagonalization theorems, or if they use something more that usual diagonalization. So my question is

is there a reasonable relativization which puts permanent in uniform $TC^0$$\mathsf{TC^0}$?

Note that I am not sure how to define oracle access for uniform $TC^0$$\mathsf{TC^0}$, I know that finding the correct definition for small complexity classes is nontrivial. Another possibility is that permanent is not complete for $sharpP$$\mathsf{\#P}$ in the relativized universe, in which case I should use some complete problem for $sharpP$$\mathsf{\#P}$ in the relativized universe in place of it, and I think $sharpP$$\mathsf{\#P}$ should have a complete problem in any reasonable relativized universe.

Do the proofs that permanent is not in uniform $TC^0$ relativize?

This is a follow up to this question, and is related to this question of Shiva Kinali.

It seems that proof in these papers (Allender, Caussinus-McKenzie-Therien-Vollmer, Koiran-Perifel) use hierarchy theorems. I want to know if the proofs are pure diagonalization theorems, or if they use something more that usual diagonalization. So my question is

is there a reasonable relativization which puts permanent in uniform $TC^0$?

Note that I am not sure how to define oracle access for uniform $TC^0$, I know that finding the correct definition for small complexity classes is nontrivial. Another possibility is that permanent is not complete for $sharpP$ in the relativized universe, in which case I should use some complete problem for $sharpP$ in the relativized universe in place of it, and I think $sharpP$ should have a complete problem in reasonable relativized universe.

Do the proofs that permanent is not in uniform $\mathsf{TC^0}$ relativize?

This is a follow up to this question, and is related to this question of Shiva Kinali.

It seems that the proofs in these papers (Allender, Caussinus-McKenzie-Therien-Vollmer, Koiran-Perifel) use hierarchy theorems. I want to know if the proofs are "pure" diagonalization theorems, or if they use something more that usual diagonalization. So my question is

is there a reasonable relativization which puts permanent in uniform $\mathsf{TC^0}$?

Note that I am not sure how to define oracle access for uniform $\mathsf{TC^0}$, I know that finding the correct definition for small complexity classes is nontrivial. Another possibility is that permanent is not complete for $\mathsf{\#P}$ in the relativized universe, in which case I should use some complete problem for $\mathsf{\#P}$ in the relativized universe in place of it, and I think $\mathsf{\#P}$ should have a complete problem in any reasonable relativized universe.