Apakah

Saya pikir saya akan membagikan pertanyaan ini karena mungkin menarik bagi pengguna lain di sini.

Asumsikan bahwa fungsi yang berada dalam kelas yang seragam (seperti ) juga berada dalam kelas kecil yang tidak seragam (seperti , yaitu tidak seragam ), apakah ini menyiratkan bahwa fungsi tersebut terkandung dalam suatu kelas seragam yang lebih kecil (seperti )? Jika jawaban untuk pertanyaan ini positif, berapakah kelas kompleksitas seragam terkecil yang berisi ? Jika negatif, dapatkah kita menemukan contoh alami yang menarik? $NP$ $AC^0/poly$ $AC^0$ $P$ $NP \cap AC^0/poly$

Apakah terkandung dalam ? $AC^0/poly \cap NP$ $P$

Catatan: Seorang teman telah sebagian menjawab pertanyaan saya secara offline, saya akan menambahkan jawabannya jika dia tidak menambahkannya sendiri.

Pertanyaannya adalah upaya kedua saya untuk memformalkan pertanyaan informal berikut:

Bisakah ketidakseragaman membantu kita dalam menghitung masalah seragam alami?

Terkait:

Apakah ada kandidat untuk masalah alami dalam ? $P/poly−P$

cc.complexity-theory circuit-complexity uniformity Kaveh
sumber

@ Kaveh: Mungkin pertanyaan yang menarik adalah menanyakan masalah alami dalam P / poly dan NP, tetapi tidak dalam P. (Atau mungkin ini terlalu mudah?)

Robin Kothari

@Robin: yang tampaknya menarik, tapi saya tidak yakin bahwa itu akan lebih mudah untuk menemukan masalah alam di

N P \cap P / p o l y - P

$NP \cap P/poly - P$

Kaveh

N E X P \neq E X P

$NEXP \neq EXP$

N T i m e (f) \neq D T i m e (f)

$NTime(f) \neq DTime(f)$

f

$f$

A C^{0} / p o l y

$AC^0/poly$

n

$n$

n

$n$

@ Kaveh: Mungkin Anda mungkin ingin melihat kelas YP, yang ditentukan oleh Scott Aaronson. Itu seperti P / poli, tetapi "saran" tidak dipercaya. Dengan kata lain, ini seperti NP intersect coNP, tetapi saksi hanya bisa bergantung pada panjang input. YP dalam P / poly, dan merupakan kelas yang seragam. Mungkin masalah di YP tetapi tidak di P adalah contoh dari masalah yang Anda cari. Itu akan alami, seragam, tidak dalam P, dalam P / poly, dan mungkin non-sepele karena saran harus diverifikasi oleh sirkuit.

Robin Kothari

@Kaveh: Kelas YP ("Yoda Polynomial-Time") lebih didefinisikan secara formal dalam makalah Scott "The Learnability of Quantum States" [quant-ph / 0608142]

Alessandro Cosentino

Jawaban:

$\Lambda \in NE \setminus E$ $L = \{x : |x| \in \Lambda\}$ $\Lambda \in NE \setminus E$ $L \in NP \setminus P$ $L \in AC^0/poly$

Yuval Filmus
sumber

Jawaban yang bagus Yuval!

Dai Le

Pada dasarnya transformasi yang sama digunakan dalam Buku 1974 untuk menunjukkan bahwa E ≠ NE jika dan hanya jika NP ∖ P berisi bahasa penghitungan.

Tsuyoshi Ito

| x |

$|x|$

x

$x$

x

$x$

| x |

$|x|$

| x |

$|x|$

| x |

$|x|$

Λ

$\Lambda$

Jawab pertanyaan pertama Anda: Tampaknya tidak mungkin.

$NP \cap AC^0/poly \subseteq P$ $NEXP = EXP$

$C$ $C$ $C(0^n) C(0^{n-1}1) C(0^{n-2}10) \cdots C(1^n)$

$C$ $n$ $NEXP$

Sekarang perhatikan bahasanya

$L =$ $1^n |$ $n$

$L$ $AC^0/poly$ $1^n$ $L$ $n$

$L$ $NP$ $n$ $\log n$ $O(n)$ $O(n)$

$L \in P$ $NEXP=EXP$ $O(n^c)$ $\log n$

Pertanyaan kedua Anda terbuka lebar (dan terbuka).

Ryan Williams
sumber

Mengapa Anda perlu mengambil beberapa masalah lengkap?

Yuval Filmus

Pikir itu membuat argumen lebih mudah diikuti.

Ryan Williams

Terima kasih Ryan atas jawaban dan penjelasannya yang bagus. Saya kira Anda tidak akan keberatan jika saya menerima jawaban Yuval meskipun Anda adalah orang pertama yang memposting.

Kaveh

Untuk pertanyaan Kaveh, "Bisakah ketidak-seragaman membantu kita dalam menghitung masalah-masalah seragam alami?"

$n$ $1$ $n$ $n^5$ $n$

Referensi:

Friedhelm Meyer auf der Heide, " Algoritma Pencarian Linear Polinomial untuk Masalah Knapsack n-Dimensi ", 1984

Stasys
sumber

n

$n$

2

$2$

2^{n}

$2^n$

1

$1$

N P \subseteq P / p o l y

$NP\subseteq P/poly$

@ Kaveh: Tetapi NP itu sendiri adalah OR besar dari P. "Versi waktu" P vs NP adalah: dapatkah kita mengganti OR besar ini dengan pohon keputusan aljabar deterministik kedalaman polinomial (dengan P pada daun)? Ingatlah bahwa kedalaman trivial untuk Subset-Sum adalah 2 ^ n (bukan n). Dopkin dan Lipton (1978) menunjukkan bahwa kedalaman n ^ 2/2 diperlukan, dan secara luas diyakini bahwa ini dapat ditingkatkan menjadi n ^ k untuk setiap k. Mayer auf der Heide membantah kepercayaan ini: k = 5 sudah cukup. Dengan demikian, ketidakseragaman BISA membantu, jika kita tertarik dengan kedalaman (waktu).

Stasys