Teori kompleksitas-sulit memeriksa nilai

The Fungsi utama-menghitung , diturunkan , didefinisikan sebagai jumlah bilangan prima kurang dari atau sama dengan .$\pi(x)$$x$

Kita dapat mendefinisikan masalah keputusan dari sebagai berikut:$\pi(x)$

Diberi dua angka dan , ditulis dalam biner, putuskan jika .$x$$n$$\pi(x) = n$

Seorang teman dan saya berbicara tentang masalah ini sebelumnya hari ini. Ada algoritma pseudopolinomial-waktu untuk masalah ini - cukup hitung hingga , gunakan pembagian percobaan pada setiap langkah untuk melihat berapa banyak bilangan prima, dan periksa apakah itu sama dengan . Masalahnya juga di PSPACE, karena algoritma yang baru saja saya jelaskan dapat diimplementasikan untuk menggunakan hanya ruang bantu polinomial.$x$$n$

Namun, saya mengalami kesulitan menemukan cara untuk menempatkan masalah ini ke kelas kompleksitas yang lebih rendah. Saya tidak dapat melihat cara membuat verifikasi polinomial-waktu untuk masalah ini, jadi saya tidak yakin apakah itu dalam NP, dan saya tidak bisa memikirkan cara untuk memasukkannya ke dalam hierarki polinomial sama sekali.

Apa kelas kompleksitas yang paling tepat untuk masalah ini?

Terima kasih!

Ini masalah yang sangat terbuka. Saya akan membuat sketsa beberapa kelas yang masalahnya "alami" cocok.

Definisi Anda agak canggung untuk dikerjakan, masalahnya sulit untuk disesuaikan dengan kelas kompleksitas yang ada. Bahasa yang Anda tetapkan adalah persimpangan bahasa dan { ( x , n ) | π ( x ) ≥ n } . Jadi jika misalnya { ( x , n ) | π ( x ) ≤ n } ada di kelas$\{(x,n)|\pi(x)\leq n\}$$\{(x,n)|\pi(x)\geq n\}$$\{(x,n)|\pi(x)\leq n\}$ then { ( x , n ) | π ( x ) ≥ n } akan di c o K . Hal ini membuat memberikan karakterisasi bahasa yang Anda definisikan keras karena seseorang harus menyatakan "persimpangan bahasa dalam K dengan bahasa dalam c o K " untuk memberikan batas yang paling ketat.$K$$\{(x,n)|\pi(x)\geq n\}$$coK$$K$$coK$

Masalah "Hitung " adalah masalah dalam # P , di mana # P ⊆ F P S P A C E adalah kelas masalah dari bentuk "Hitung jumlah jalur penerimaan dari polinomial TM" nondeterministic, polinomial ". Jelas kita dapat membuat TM non-deterministik yang menebak angka q ≤ x , dan kemudian (dengan AKS) menguji apakah q adalah prima.$\pi(X)$$\#P$$\#P\subseteq FPSPACE$$q \leq x$$q$

Varian keputusan adalah P P , yang merupakan kelas bahasa yang berbentuk: "Diberikan polinomial TM non-deterministik, apakah paling tidak setengah dari jalur komputasi diterima?". Keduanya { ( x , n ) | π ( x ) ≤ n } dan { ( x , n ) | π ( x ) ≥ n } mungkin dapat direduksi menjadi masalah dalam P $\#P$$PP$$\{(x,n)|\pi(x)\leq n\}$$\{(x,n)|\pi(x)\geq n\}$$PP$ (dengan melakukan beberapa fudging ke TM yang disebutkan di atas untuk menyeimbangkan jumlah jalur penerimaan).

Masalah Anda ada di C = P$_=$ melalui algoritma$\hspace{-0.06 in}\text{,}$

$\;\;\;$menebak secara non-deterministik bilangan bulat sedemikian rupa$\big[$m dan sedikit$\: 0\leq m < 2^{\lceil \hspace{.02 in}\log_{\hspace{.02 in}2}\hspace{-0.02 in}(x+1)\rceil}\big]$b
$\;\;\;$jika x < mkemudian tolak
$\;\;\;$jika b=1kemudian:
$\;\;\;\;\;$jika m < nkemudian menerima lagi tolak
$\;\;\;$ lain:
$\;\;\;\;\;$jika m prima maka terima yang lain tolak

.


Khususnya, masalah Anda juga dalam PP, karena PP ditutup di bawah pengurangan tabel kebenaran .

Dalam praktiknya, Anda mungkin mendapatkan jawabannya lebih cepat atau lebih lambat :-(

Ada perkiraan yang cukup baik untuk π (x). Jadi Anda menghitung perkiraan seperti itu, dan jika terlalu jauh Anda tahu bahwa π (x) ≠ n. Misalnya, jika n ≥ x maka saya tahu itu π (x) ≠ n tanpa menghitung apa pun.

Ada algoritma cepat yang menentukan apakah π (x) genap atau ganjil, berjalan di O (x ^ (1/2)). Anda dapat menjalankan algoritme ini dan dapat mendeteksi bahwa paritas n salah dan Anda selesai. Ini memiliki peluang lima puluh jika n adalah bilangan bulat acak mendekati π (x).

Selain itu, saya tidak tahu metode apa pun yang lebih cepat daripada menghitung π (x). Yang sangat merepotkan - jika saya menulis sebuah program yang seharusnya menghitung π (10 ^ 25), dan saya mendapatkan hasil yang tidak jelas salah, maka tidak ada cara untuk memeriksa bahwa hasil saya benar selain mengulangi perhitungan. Dan Anda tidak bisa hanya mengulangi perhitungan menggunakan program saya, Anda perlu menulis program yang berbeda, jika tidak, Anda tidak akan mendeteksi jika program saya memiliki bug yang membuatnya menghitung fungsi yang sedikit berbeda dari π (x).

π (x) dapat dihitung dengan mudah di sekitar O (n ^ (2/3)), dan lebih cepat dengan beberapa matematika yang sangat dalam.