Apakah ada lebih banyak masalah waktu polinomial dengan kompleksitas batas bawah?

Saya mencari lebih banyak masalah di dengan kompleksitas waktu klasik batas bawah. Beberapa orang mungkin bertanya-tanya bagaimana Anda dapat membuktikan batas bawah seperti itu. Lihat di bawah.$P$

Batas Bawah Eksponensial:

Klaim: Jika Anda memiliki masalah yaitu -complete di bawah pengurangan polinomial, maka ada konstanta sehingga tidak dapat dipecahkan dalam waktu. E X P T I M E α ∈ R X O ( 2 n α$X$$EXPTIME$$\alpha \in \mathbb{R}$$X$$O(2^{n^{\alpha}})$

Ide Bukti: Berdasarkan teorema hierarki waktu, ada masalah dalam waktu yang tidak dalam waktu waktu. Selanjutnya, harus ada pengurangan polinomial dari ke . Oleh karena itu, ada konstan sehingga pengurangan ini mengambil contoh dari ukuran untuk Y ke sebuah contoh dari ukuran n c untuk X . The batas bawah untuk Y dari O ( 2 n 1 - ε ) pergeseran waktu untuk batas bawah untuk X dari OO ( 2 n ) o ( 2 $Y$$O(2^n)$YXc$o(\frac{2^n}{n})$$Y$$X$$c$$n$$Y$$n^c$$X$$Y$$O(2^{n^{1-\epsilon}})$$X$waktu.$O(2^{n^{\frac{1-\epsilon}{c}}})$

Batas Bawah Polinomial:

Beberapa - masalah lengkap memiliki parameterisasi yang bagus menjadi masalah waktu polinomial. Pertimbangkan masalah X dari sebelumnya. Misalkan kita memiliki parameterisasi k - X untuk X sedemikian rupa sehingga:$EXPTIME$$X$$k$$X$$X$

• Untuk setiap tetap , k - X dalam waktu polinomial.$k$$k$$X$

$k$$k$$X$$X$

Sebuah contoh:

Salah satu contoh masalah yang muncul adalah persimpangan non-kekosongan untuk tree automata. Yaitu, mengingat daftar terbatas automata pohon, apakah ada pohon yang secara bersamaan memenuhi semua automata?

$EXPTIME$$k$$k$$n^{\Theta(k)}$

Pertanyaan:

$EXPTIME$

Inilah salah satu yang melibatkan permainan 2 pemain kerikil. Anda memutuskan apakah itu wajar (:

T. Kasai, A. Adachi, S. Iwata. Kelas permainan kerikil dan menyelesaikan masalah. 1979

Teorema 3.1 memiliki kelengkapan EXPTIME pebbling. Teorema 3.3 memiliki kemudahan k-pebble.

A. Adachi, S. Iwata, T. Kasai. Beberapa Masalah Permainan Kombinatorial Memerlukan Waktu Omega (n ^ k). 1984

Teorema 3.2 memiliki batas bawah pada k-pebble. Terakhir, Anda mungkin juga tertarik pada:

T. Kasai dan S. Iwata. Masalah yang sulit diatasi secara bertahap dan batas bawah ruang log yang tidak ditentukan. 1985

Sayangnya bahwa ini semua di balik paywalls :(