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

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 .

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 $2^{f(n)}$ , $A$ dapat mengunjungi masing-masing negara yang berbeda, sehingga tidak dapat memperoleh apa pun dengan menjalankan lebih dari $2^{f(n)}$ waktu.

Oleh karena itu:

$\mathbf{NP}$ $\subseteq \mathbf{PSPACE}$

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

Penjelasannya sederhana: masalah $Q$ $\in$ $\mathbf{NP}$ memiliki sertifikat panjang polinomial $y$ . Algoritma yang menguji semua sertifikat yang mungkin adalah algoritma yang menentukan $Q$ dalam waktu $\large 2^{n^{O(1)}}$ .

Persyaratan ruangnya adalah:

• $y$ (polinomial dalam$n$ )
• $y$$y$

$Q$

Contoh:

$\varphi$$x_1 \dots x_n$$m$$f$$f:\{x_1\dots x_n\} \rightarrow \{0,1\}$

Ini menyatakan bahwa:

• $2^n$
• $f$$O(m)$$\varphi$$O(m)$

$A$

Oleh karena itu:

$\in \mathbf{PSPACE}$$\mathbf{NP}$ $\subseteq \mathbf{PSPACE}$

Iya. Berikut ini sketsa bukti langsung.

$\mathrm{NP}$$M$$p$$M$$n$$p(n)$$p(n)$

$c$$M$$M$$c$$c^{p(n)}$$n$$c^{p(n)}$$p(n)$$c$$p(n)$$M$$i$$i$$i$$6$

$0\dots 0$$M$$c-1$$c^{p(n)}p(n)$$2p(n)$