Apakah ALogTime! = PH sulit dibuktikan (dan tidak dikenal)?

Lance Fortnow baru-baru ini mengklaim bahwa membuktikan L! = NP harus lebih mudah daripada membuktikan P! = NP :

Pisahkan NP dari ruang Logaritmik. Saya memberikan empat pendekatan dalam survei pra-blog 2001 tentang diagonalisasi (Bagian 3) meskipun tidak ada yang berhasil. Seharusnya lebih mudah daripada memisahkan P dari NP.

Bagian 3 dalam survei terkait mengklaim bahwa tidak ada hasil kehancuran oracle yang berarti:

Sementara pertanyaan P! = NP tetap cukup tangguh, pertanyaan L! = NP tampaknya jauh lebih mudah ditelusuri. Kami tidak punya alasan untuk menganggap pertanyaan ini sulit. Kurangnya model relativisasi yang baik untuk ruang berarti kita tidak memiliki model oracle yang berarti di mana L dan NP runtuh. Juga karena L adalah kelas yang seragam, batasan Razborov-Rudich [RR97] tidak berlaku.

Sebuah pertanyaan tentang hambatan relativiasi yang dikenal untuk L! = NP di situs ini mendapat jawaban yang menunjukkan bahwa TQBF menyelesaikan masalah PSPACE dapat digunakan sebagai ramalan untuk mendapatkan keruntuhan seperti itu. Keberatan tentang apakah ini adalah model oracle yang berarti tampaknya juga dijawab.

Tetapi bahkan jika saya akan mengerti mengapa "kita tidak memiliki model oracle yang berarti di mana L dan NP runtuh" harus dianggap sebagai pernyataan yang benar, saya masih ragu apakah membuktikan L! = NP lebih layak daripada membuktikan P! = NP. Jika membuktikan L! = NP harus benar-benar lebih mudah daripada membuktikan P! = NP, maka membuktikan ALogTime! = PH harus secara pasti berada dalam jangkauan. (Artikel survei mengisyaratkan kemungkinan untuk memisahkan dari ) Saya kira ALogTime! = PH masih terbuka, dan saya ingin tahu apakah ada alasan bagus untuk berharap bahwa itu akan sulit untuk dibuktikan. $\Sigma_2^p$ $L$

cc.complexity-theory reductions relativization Thomas Klimpel
sumber

Lance Fortnow 7:03 AM, 13 Mei 2016 : "Biarkan saya ulangi poin saya. Biarkan AP menjadi bolak-balik polytime (dikenal sebagai PSPACE tidak terkait dan dengan demikian berbeda dari L). Kemudian tidak ada model relativisasi yang diketahui keduanya membuat L = NP untuk beberapa oracle tetapi memisahkan L dari AP untuk semua oracle. "

Thomas Klimpel

Jawaban:

Tidak yakin mengapa Fortnow mengatakan bahwa "tidak ada model yang berarti di mana dan runtuh" ... menurut saya QBF harus membuat mereka runtuh, di bawah model oracle Ruzzo-Simon-Tompa yang biasa (dan tautan yang Anda masukkan setuju). Perhatikan bahwa model oracle ini juga memiliki keanehannya: kita memiliki jika dan hanya jika untuk setiap oracle , sehingga setiap oracle yang menyaksikan pemisahan akan menyiratkan pemisahan yang tidak ter-relativisasi. $L$ $NP$ $L = NL$ $L^A = NL^A$ $A$

$NC1$ $ALogTime = NP$ $NC1$ $NP$ $NC1$

Selain itu, saya tahu tidak ada alasan khusus untuk percaya bahwa "sulit untuk dibuktikan" selain dari pengamatan bahwa banyak orang telah mencoba dan belum ada yang berhasil.

Ryan Williams
sumber

L = N L

$L = NL$

L^{A} = N L^{A}

$L^A = NL^A$

A

$A$

L

$L$

Saya percaya ada bukti pernyataan di koran yang saya tautkan. Mengenai kalimat kedua Anda: apakah Anda bertanya mengapa Fortnow mengatakan Razborov-Rudich tidak berlaku? Jika demikian, maksudnya adalah bahwa penghalang pembuktian alami seperti yang dipahami secara umum hanya berlaku jika model yang Anda lawan lebih rendah tidak seragam, misalnya P / poli.

Ryan Williams

Ah, saya salah membaca: Saya pikir penghalang yang tidak berlaku adalah relativization, bukan bukti alami, maaf. Yang ingin saya tanyakan adalah: mengapa relativisasi menjadi penghalang untuk P vs NP tetapi tidak L vs NL, secara moral? (Karena itu, tidak ada kaitannya dengan pertanyaan.)

Michaël Cadilhac

Singkatnya, itu karena model oracle RST tidak membiarkan Anda membuat langkah-langkah nondeterministic kecuali pita oracle kosong. (Alasan untuk itu tidak jelas; pada dasarnya beberapa hasil tidak akan hilang tanpa itu.) Argumen yang sebenarnya lebih rumit ...

Ryan Williams

Gagasan naif untuk membuktikan ALogTime! = PH: Masalah nilai rumus Boolean selesai untuk ALogTime dalam pengurangan waktu log yang deterministik . Oleh karena itu jika ALogTime = PH, maka PH = coNP = ALogTime, dan karenanya masalah nilai rumus Boolean akan selesai di bawah pengurangan waktu log deterministik untuk coNP. Oleh karena itu akan ada pengurangan waktu log deterministik dari masalah tautologi ke masalah nilai formula Boolean.

Pengurangan waktu log deterministik seharusnya tidak berbahaya, mereka tidak dapat berkontribusi banyak untuk solusi masalah tautologi. Mereka hanya formalisasi yang bagus apa artinya pengurangan hanya bisa bekerja secara lokal. Karenanya tugas yang tersisa adalah untuk memahami mengapa masalah tautologi tidak dapat diubah menjadi masalah nilai formula Boolean dengan pengurangan yang sangat lokal. Saya masih tidak melihat bagaimana melakukan itu, tetapi setidaknya tugas yang tersisa sangat jelas, sehingga saya setidaknya memiliki kesempatan untuk memahami mengapa itu sulit (atau tidak).

Thomas Klimpel
sumber