Apakah ada kelas kompleksitas yang ditetapkan dengan bilangan real?

Seorang siswa baru-baru ini meminta saya untuk memeriksa bukti kekerasan NP untuk mereka. Mereka melakukan pengurangan sepanjang garis:

Saya mengurangi masalah ini $P'$ yang dikenal sebagai NP-lengkap untuk masalah saya $P$ (dengan banyak-satu pengurangan poli-waktu), jadi $P$ adalah NP-keras.

Jawaban saya pada dasarnya:

Karena $P$ memiliki instance dengan nilai-nilai dari $\mathbb{R}$ , itu sepele bukan Turing-computable sehingga Anda dapat melewati pengurangan.

Meskipun secara formal benar, saya tidak berpikir pendekatan ini berwawasan luas: kami tentu ingin dapat menangkap "kompleksitas yang melekat" dari masalah keputusan (atau optimasi) yang bernilai nyata, mengabaikan keterbatasan yang kami hadapi dalam berurusan dengan masalah nyata. angka; menyelidiki masalah ini adalah untuk hari lain.

Tentu saja, tidak selalu semudah mengatakan, "versi terpisah dari Subset Sum adalah NP-lengkap, jadi versi kontinu adalah 'NP-hard' juga". Dalam hal ini, pengurangannya mudah tetapi ada kasus terkenal dari versi kontinu yang lebih mudah, misalnya pemrograman linier vs integer.

Terpikir oleh saya bahwa model RAM secara alami meluas ke bilangan real; biarkan setiap register menyimpan angka nyata dan memperpanjang operasi dasar yang sesuai. Model biaya seragam masih masuk akal - sama halnya dalam kasus diskrit - sementara yang logaritmik tidak.

Jadi, pertanyaan saya bermuara pada: apakah ada gagasan tentang kompleksitas masalah bernilai nyata? Bagaimana mereka berhubungan dengan kelas diskrit "standar"?

^{Pencarian Google menghasilkan beberapa hasil, misalnya ini , tetapi saya tidak memiliki cara untuk mengatakan apa yang ditetapkan dan / atau berguna dan apa yang tidak.}

Iya. Ada.

Ada model real-RAM / BSS yang disebutkan dalam jawaban lain. Model memiliki beberapa masalah dan AFAIK tidak banyak kegiatan penelitian tentang hal itu. Boleh dibilang, itu bukan model perhitungan yang realistis .

Gagasan yang lebih aktif dari komputasi nyata adalah model komputasi tipe yang lebih tinggi. Ide dasarnya adalah Anda mendefinisikan kompleksitas untuk fungsi tipe yang lebih tinggi dan kemudian menggunakan fungsi tipe yang lebih tinggi untuk mewakili bilangan real.

Studi tentang kompleksitas fungsi tipe yang lebih tinggi kembali ke setidaknya ke [1]. Untuk pekerjaan terbaru, periksa makalah Akitoshi Kawamura tentang kerumitan operator nyata.

Referensi klasik untuk kompleksitas fungsi nyata adalah buku Ker-I Ko [2]. Bab 6 buku yang lebih baru dari Klause Weihrauch [3] juga membahas kompleksitas komptasi nyata (tetapi lebih fokus pada komputabilitas daripada kompleksitas).

• [1] Stephen Cook dan Bruce Kapron, "Karakterisasi fungsi dasar yang layak dari tipe terbatas", 1990.

• [2] Ker-I Ko, "Kompleksitas Komputasi Fungsi Riil", 1991.

• [3] "Analisis Komputasi" Klaus Weihrauch, 2000.

Model yang Anda gambarkan dikenal sebagai model Blum-Shub-Smale (BSS) (juga model Real RAM) dan memang digunakan untuk mendefinisikan kelas kompleksitas.

Beberapa masalah yang menarik dalam domain ini adalah kelas , N P R , dan tentu saja pertanyaan apakah P R = N P R . Dengan P R yang kami maksud masalahnya adalah polinomially dapat ditentukan, N P R adalah masalahnya dapat diverifikasi secara polinomi. Ada kekerasan / kelengkapan pertanyaan tentang kelas N P R . Sebuah contoh dari N P R masalah lengkap adalah masalah Q P S , Kuadrat Polinomial System, di mana input adalah polinomial nyata dalam$P_R$$NP_R$$P_R$$NP_R$$P_R$$NP_R$$NP_R$$NP_R$$QPS$ variabel, dan p 1 , . . . , P n ⊆ R [ x 1 , . . . , x n ] derajat paling banyak 2, dan setiap polinomial memiliki paling banyak 3 variabel. Pertanyaannya apakah ada solusi nyata yang umum R n , sehingga p 1 ( a ) , p 2 ( a ) , . . . p n ( a ) = $m$$p_1, ..., p_n$ $\subseteq$ $R[x_1, ..., x_n]$$R^n$$p_1(a), p_2(a), ... p_n(a) = 0$. Ini adalah masalah lengkap.$NP_R$

Tetapi yang lebih menarik, ada beberapa penelitian tentang hubungan antara (Probalistically Checkable Proofs) dengan Reals, yaitu kelas P C P R , dan bagaimana kaitannya dengan model perhitungan aljabar. Model BSS panci untuk semua N P lebih real. Ini adalah standar dalam literatur, dan apa yang kita ketahui saat ini adalah bahwa N P R memiliki "transparan bukti lama", dan "bukti pendek transparan". Dengan "bukti panjang transparan" berikut ini tersirat: N P R terkandung dalam P C P R ( p o l $PCP$$PCP_R$$NP$$NP_R$$NP_R$ . Ada juga ekstensi yang mengatakan, "Versi Pendek Hampir (kira-kira)" juga benar. Bisakah kita menstabilkan bukti dan mendeteksi kesalahan dengan memeriksa komponen (nyata) yang jauh lebih sedikit daripada n ? Hal ini menimbulkan pertanyaan tentang keberadaan nol untuk (sistem) polinomial univariat yang diberikan oleh program garis lurus. Juga, dengan "bukti panjang transparan" yang kami maksud$PCP_R(poly, O(1))$$n$

1. "transparan" - Hanya, untuk dibaca,$O(1)$

2. panjang - jumlah superpolinomial dari komponen nyata.

Buktinya terkait dengan , dan yakin salah satu cara untuk melihat masalah dihargai nyata adalah bagaimana mungkin terkait dengan Subset Sum - algoritma pendekatan bahkan untuk masalah nyata dihargai akan -seperti yang menarik untuk optimasi - Linear Programming kita tahu adalah di kelas F P , tapi ya itu akan menarik untuk melihat bagaimana approximatability mungkin dampak kelengkapan / kekerasan untuk kasus N P R masalah. Juga, pertanyaan lain adalah N P R = c o - N P R ? $3SAT$$FP$$NP_R$$NP_R$ $=$ $co\text{-}NP_R$

Sambil memikirkan kelas , ada kelas penghitungan yang juga didefinisikan untuk memungkinkan alasan tentang aritmatika polinomial. Sedangkan # P adalah kelas fungsi f yang didefinisikan lebih dari { 0 , 1 } ∞ → N yang memiliki waktu polinom Turing mesin M dan p polinomial dengan properti yang ∀ n ∈ N , dan x ∈ { 0 , 1 } n , f ( x $NP_R$$\#P$$f$$\{0,1\}^\infty$ $\rightarrow$ $\mathbb{N}$$M$$p$$\forall n$$\in$$\mathbb{N}$$x$$\in$$\{0,1\}^{n}$$f(x)$menghitung jumlah string { 0 , 1 } p ( n ) yang diterima Mesin Turing M { x , y } . Untuk real kami memperluas ide ini ada mesin BSS aditif - mesin BSS yang hanya melakukan penambahan, dan perkalian (tidak ada divisi, tidak ada pengurangan). Dengan mesin BSS aditif (node ​​dalam perhitungan hanya memungkinkan penambahan, dan multiplikasi) model untuk # P menjadi salah satu di mana penghitungan berada di atas vektor yang diterima oleh mesin BSS aditif. Jadi, kelas penghitungan adalah # P a d $y \in$$\{0,1\}^{p(n)}$$M$$\{x,y\}$$\# P$$\#P_{add}$ kelas ini berguna dalam mempelajari angka Betti, dan juga karakteristik Euler.