Apa masalah PSPACE-lengkap pseudo-polinomial yang dikenal?

tolong dapatkah Anda memberikan referensi, atau memberikan contoh-contoh khusus dari masalah PSPACE-lengkap yang dapat dipecahkan dalam waktu semu-polinomial?

Catatan tambahan:

Definisi waktu polinom pseudo: http://en.wikipedia.org/wiki/Pseudo-polynomial_time

Sebagai balasan atas beberapa komentar yang disebutkan sebelumnya. Saya telah bertanya sebelumnya apakah ada masalah yang menyelesaikan PSPACE yang memiliki FPTAS. Jawaban yang mengejutkan adalah YA!

Apakah Ada Masalah Lengkap PSPACE tertentu yang memiliki algoritma FPTAS?

Karena itu, ini adalah pertanyaan lanjutan.

(Perhatikan bahwa dugaan EXP berlaku untuk NP kelas kompleksitas, namun ada masalah NP-complete yang dapat dipecahkan dalam waktu psuedo-polinomial!)

Tambahan ... Sasho Nikolov bertanya tentang FPT dan Pspace. Saya tahu bahwa ada masalah FPT yang Pspace, Exp, Exp Space selesai dll ... Sayangnya saya tidak punya referensi ... Akan memperbaiki ketika saya ingat

Terima kasih!!!

Zelah

cc.complexity-theory complexity-classes Zelah 02
sumber

yang eksponensial waktu hipotesis menunjukkan bahwa masalah tersebut mungkin sulit didapat, tapi saya bukan ahli.

Artem Kaznatcheev

Apa yang Anda maksud dengan masalah pseudopolinomial? Saya memilih untuk menutup pertanyaan sebagai off topic, dengan asumsi bahwa yang Anda maksud adalah masalah PSPACE-complete yang dapat diselesaikan dalam waktu pseudopolinomial (masalah seperti itu jelas tidak ada jika PSPACE⊈DTIME [2 ^ (polylog n)], yang merupakan hipotesis jauh lebih lemah daripada hipotesis waktu eksponensial). Jika asumsi saya tidak benar, saya dapat (secara virtual) mengambil kembali suara dekat saya.

Tsuyoshi Ito

@ Tsuyoshi, @ Artem: Apakah kalian membingungkan semu-polinomial dengan kuasi-polinomial?

Robin Kothari

@Robin: Ya, saya membingungkan pseudo-polinomial dengan kuasi-polinomial. Terima kasih telah menunjukkannya.

Tsuyoshi Ito

@Robin: Begitu juga aku, salahku!

Artem Kaznatcheev

Jawaban:

$x_0,\ldots,x_{2n+1}$ $x_{2i},x_{2i+1}$ $i$ $x_{2i}$ $i$ $x_{2i+1}$ $\exists y_0 \forall y_1 \cdots \sum_{i}y_i = k$ $y_i$ $x_{2i}$ $x_{2i+1}$

$k$ $Q_iy_iQ_{i+1}y_{i+1}\cdots Q_ny_n\sum_{j=i}^{n}y_j = k$ $Q_j$ $\exists$ $\forall$ $i-1$ $i$ $x_{2(i-1)}$ $x_{2i-1}$ $i$ $\exists$ $\forall$

Dave
sumber

$x \in \{0,1\}^*$ $w = 1x$ $w$ $w$ $w = 10...01x$

Bahkan bekerja untuk EXP.

5501
sumber

Tetapi bukankah pseudopolinomial berarti bahwa waktu berjalan adalah polinomial dalam ukuran bobot (bukan ukuran deskripsi bobot) yang sama dengan ukuran deskripsi jika bobot diberikan secara unary?

5501

@ 5501 Yang saya maksud adalah bukti bahwa QBF adalah PSPACE-complete tidak berfungsi lagi jika input untuk QBF diberikan secara unary.

Marc Bury

@ Mark Gille Tentu saja, masalahnya adalah orang dengan input yang diberikan dalam biner. Ini adalah PSPACE-complete. Dan algoritma waktu pseudopolinomial adalah algoritma yang berjalan dalam waktu polinomial jika bobot diberikan secara unary. Jika Anda memiliki instance Knapsack dengan bobot di unary, maka bukti kelengkapan NP juga tidak berfungsi. Singkatnya: kelengkapan = bobot yang diberikan dalam biner, algoritma pseudopolinomial = bobot dalam unary.

5501

P

$P$

Tentu saja, masalahnya adalah buatan. Tetapi jawaban untuk pertanyaan sebelumnya juga dibuat-buat. Di sisi lain: "Apa definisi alami yang baik?" Buku Komputasi Kompleksitas Papadimitriou, apge 216 cukup menarik.

5501

Contoh favorit saya (karena Grzegorczyk):

$\mathcal G_2$ $x + y, x y,$ $(x, y)$ $x$ $y$ $x \dot- y$ $y > x$

$\mathcal G_2$ $\mathcal G_2$

Ben Standeven
sumber