Apakah bukti bahwa permanen tidak berseragam

Ini adalah tindak lanjut dari pertanyaan ini , dan terkait dengan pertanyaan Siwa Kinali ini.

Tampaknya bukti dalam makalah ini ( Allender , Caussinus-McKenzie-Therien-Vollmer , Koiran-Perifel ) menggunakan teorema hierarki. Saya ingin tahu apakah buktinya adalah teorema diagonalisasi " murni ", atau apakah mereka menggunakan sesuatu yang lebih dari diagonalisasi biasa. Jadi pertanyaan saya adalah

apakah ada perelatifan wajar yang menempatkan permanen berseragam $\mathsf{TC^0}$ ?

Perhatikan bahwa saya tidak yakin bagaimana mendefinisikan akses oracle untuk seragam , saya tahu bahwa menemukan definisi yang benar untuk kelas kompleksitas kecil adalah nontrivial. Kemungkinan lain adalah bahwa permanen tidak lengkap untuk di alam semesta yang mengalami relativisasi, dalam hal ini saya harus menggunakan beberapa masalah lengkap untuk di alam semesta yang direlatifikasi menggantikannya, dan saya pikir seharusnya memiliki masalah yang lengkap dengan cara apa pun yang masuk akal alam semesta yang direlatifikasi. $\mathsf{TC^0}$ $\mathsf{\#P}$ $\mathsf{\#P}$ $\mathsf{\#P}$

cc.complexity-theory lower-bounds relativization permanent Kaveh
sumber

Bagaimana Anda mendefinisikan versi permanen dari relativized? Atau Anda mencari dunia yang relativized di mana PP⊆TC ^ 0?

Tsuyoshi Ito

@Tsuyoshi: Masalahnya adalah saya tidak yakin tentang bukti bahwa makhluk permanen lengkap untuk

. Sepertinya saya bahwa bukti bahwa permanen tidak seragam

bekerja juga untuk setiap masalah lainnya lengkap. Sebuah perelatifan wajar yang menempatkan

di dalam

akan menjawab pertanyaan saya.

s h a r p P

$sharpP$

T C^{0}

$TC^0$

s h a r p P

$sharpP$

T C^{0}

$TC^0$

Kaveh

Saya tidak yakin apa yang Anda maksud dengan relativisasi "masuk akal". Untuk dua kelas kompleksitas, seseorang dapat menyamakannya dengan mengambil oracle yang cukup kuat, bukan? Misalnya

. (Kelas pertama adalah

dengan "QBF gates".)

A C 0^{P S P A C E} = P S P A C E = P S P A C E^{P S P A C E}

$AC0^{PSPACE} = PSPACE = PSPACE^{PSPACE}$

A C 0

$AC0$

Ryan Williams

@Ryan: Saya pikir cara mendefinisikan akses oracle itu penting, dan jika definisi itu tidak benar maka hal-hal aneh bisa terjadi. Sebagai contoh, lihat ini cs.toronto.edu/~sacook/homepage/rel-web.ps . (catatan: Saya tidak ingat bahwa mereka juga membahas

) Mesin dengan sumber daya yang lebih banyak dapat mengajukan pertanyaan yang lebih rumit daripada yang lebih terbatas dari oracle yang sama dan itulah alasan mengapa kami tidak memiliki (masuk akal) ) relativization yang akan membuat DTime (n) = DTime (

), jadi bagi saya sepertinya tidak semaju yang Anda katakan, bukan?

T C^{0}

$TC^0$

n^{2}

$n^2$

Kaveh

(hierarki waktu log)

, jadi seharusnya tidak ada relativisasi yang masuk akal yang akan membuat

. Aku merasakan sesuatu yang mungkin salah dengan alasan saya di baris sebelumnya, kita tahu

A C^{0} = L H

$AC^0 = LH$

\subset P H \subseteq P S p a c e

$\subset PH \subseteq PSpace$

A C^{0} = P S p a c e

$AC^0 = PSpace$

L H \subset P H

$LH \subset PH$

Kaveh

Jawaban:

Setiap pemisahan kelas yang ditutup dengan "sumber daya polinomial" memiliki oracle yang membuat mereka setara. (Ini disediakan mekanisme oracle adil dan memungkinkan kedua model mesin untuk membuat pertanyaan panjang polinomial dan tidak lebih.)

Biarkan menjadi " dengan gerbang untuk oracle ". Membiarkan menjadi bahasa lengkap di bawah pengurangan , kita memiliki , di mana dalam mekanisme oracle untuk $TC0^{O}$ $TC0$ $O$ $O$ $PSPACE$ $TC0$ $TC0^{O} = PSPACE = PSPACE^{O} = PP^{O}$ $PSPACE$ $AC0$ $TC0$ $LOGSPACE$ $P$ $NP$ $PH$ $PP$ $AC0$ $AC0[2]$ ).

In the collection of proofs you cite, I believe most of them (if not all) work by assuming $TC0 = PP$ and deriving a contradiction. These kinds of results are called "indirect diagonalization". So a relativization of their proof would have to say: "if $TC0^{O} = PP^{O}$ , then contradiction..." but this assumption is actually true for some oracles $O$ .

In the comments, it was pointed out that $LOGSPACE^{O} = PSPACE^{O}$ in the way that I am using it. These are just subtleties with the oracle mechanism. On the LOGSPACE side, the query tape cannot be part of the space bound, since queries are polynomial length. On the PSPACE side, the query tape is taken as part of the space bound. That was to make things "fair". But if you give them exactly the same oracle mechanism then indeed you can separate them again by diagonalization. For instance, if queries do not count towards the space bound, then in PSPACE^{PSPACE} you can ask exponentially long questions to PSPACE, so this in fact contains EXPSPACE. I apologize for not saying this explicitly earlier.

Space-bounded computation is very subtle with respect to oracles. See page 5 of this article by Fortnow for a good summary of why oracle and space-bounded computation don't always mix.

Ryan Williams
sumber

Thanks for the comment about PSPACE^{PSPACE} containing EXPSPACE in the model that we used for LOGSPACE. My confusion has been cleared.

Robin Kothari

See also Aehlig, Cook and Nguyen, Relativizing small complexity classes and their theories.

Yuval Filmus