Bisakah Masalah NP-Lengkap diselesaikan menggunakan paling banyak ruang polinomial (tetapi saat menggunakan waktu eksponensial?)

12

Saya membaca tentang NPC dan hubungannya dengan PSPACE dan saya ingin tahu apakah masalah NPC dapat dipecahkan dengan menggunakan algoritma dengan persyaratan ruang polinomial kasus terburuk, tetapi berpotensi mengambil waktu eksponensial (2 ^ P (n) di mana P adalah polinomial).

Selain itu, dapatkah itu digeneralisasi ke EXPTIME secara umum?

Alasan saya menanyakan hal ini adalah karena saya menulis beberapa program untuk menyelesaikan kasus NPC yang merosot, dan mereka dapat mengkonsumsi RAM dalam jumlah sangat besar untuk hard case, dan saya bertanya-tanya apakah ada cara yang lebih baik. Untuk referensi, lihat https://fc-solve.shlomifish.org/faq.html .

Ikan Shlomi
sumber

Jawaban:

27

Secara umum, berikut ini berlaku untuk algoritma apa pun:

  1. Misalkan A adalah algoritma yang berjalan dalam waktu f(n) . Maka A tidak dapat mengambil lebih dari f(n) spasi, karena menulis f(n) bit membutuhkan waktu f(n) .
  2. Misalkan A adalah algoritma yang membutuhkan ruang f(n) . Kemudian dalam waktu 2f(n) , A dapat mengunjungi masing-masing negara yang berbeda, sehingga tidak dapat memperoleh apa pun dengan menjalankan lebih dari 2f(n) waktu.

Oleh karena itu:

NP PSPACE

Statemement dikenal sebagai bagian dari hubungan antar kelas, seperti yang digambarkan oleh diagram berikut:

hubungan antar kelas

Penjelasannya sederhana: masalah Q NP memiliki sertifikat panjang polinomial y . Algoritma yang menguji semua sertifikat yang mungkin adalah algoritma yang menentukan Q dalam waktu 2nO(1) .

Persyaratan ruangnya adalah:

  • y (polinomial dalamn )
  • yy

Q


Contoh:

φx1xnmff:{x1xn}{0,1}

Ini menyatakan bahwa:

  • 2n
  • fO(m)φO(m)

A

Oleh karena itu:

PSPACENP PSPACE

salmon asap
sumber
1
Mengapa EXPSPACE dan EXPTIME terkait? Saya pikir waktu dan ruang adalah sumber daya yang berbeda. Salah satu contoh yang muncul dalam pikiran adalah melanggar skema crypto, yang akan membutuhkan EXPTIME, tetapi ruang konstan
WeCanBeFriends
6
f(n)f(n)2f(n)
Apakah f (n) berbeda dengan O (n) dalam contoh Anda?
WeCanBeFriends
1
@WeCanBeFriends Seseorang tidak dapat menggunakan waktu eksponensial dengan ruang konstan: Anda memerlukan setidaknya ruang yang digunakan untuk menghitung sampai angka eksponensial itu (misalnya penghitung program dari bahasa assembly), yang jumlahnya banyak (logaritmik dalam eksponensial)
gigabytes
4
PEXPTIME
9

Iya. Berikut ini sketsa bukti langsung.

NPMpMnp(n)p(n)

cMMccp(n)ncp(n)p(n)cp(n)Miii6

00Mc1cp(n)p(n)2p(n)

David Richerby
sumber