Apa kelas reduksi terkecil di mana ada masalah

Adalah umum untuk mendefinisikan kelengkapan sehubungan dengan reduksi banyak-satu ruang log. $P$

Saya mencari kelas kerumitan sedemikian rupa sehingga ada masalah - lengkap dan banyak-satu pengurangan - . $C \subseteq \mathsf{L}$ $\mathsf{P}$ $C$

Berapakah pengurangan kelas banyak-satu terkecil yang diketahui sehingga HornSAT selesai untuk dalam pengurangan- ? $C$ $\mathsf{P}$ $C$

Pertanyaan awalnya diposting di CS tanpa jawaban.

cc.complexity-theory complexity-classes Mohammad Al-Turkistany
sumber

Mungkin maksud Anda semua masalah non-sepele: bahasa kosong dan bahasa yang komplemennya kosong tidak dapat lengkap.

Sasho Nikolov

@SashoNikolov Tentu, saya tidak tertarik dengan bahasa yang sepele!

Mohammad Al-Turkistany

Saya tidak mengerti pertanyaannya. Jika C = P maka semua masalah dalam P kecuali yang sepele selesai untuk P dalam pengurangan C, dan ini adalah kasus yang tidak tergantung pada apa itu C.

Kaveh

@ Kaveh Apa kelas

terkecil seperti itu ? Misalnya, apakah HornSAT lengkap untuk

bawah

Reduksi?

C

$C$

P

$P$

N C^{1}

$NC^1$

Mohammad Al-Turkistany

Saya berbagi kebingungan Kaveh tentang paragraf pertama. Tetapi mengenai pertanyaan biru, penyandian yang wajar dari Horn-SAT adalah P-selesai di bawah pengurangan DLOGTIME.

Emil Jeřábek

Jawaban:

Mudah untuk menunjukkan bahwa Masalah Nilai Sirkuit lengkap untuk pengurangan bawah (lihat komentar András di bawah). $\mathsf{P}$ $\mathsf{AC^0}$

Untuk contoh lebih mudah mempertimbangkan

A = {⟨ M, x, y ⟩ ∣ M accepts x in | y | steps}

$A = \{\langle M,x,y\rangle \mid \text{$M$ accepts $x$ in $|y|$ steps} \}$

Jika kelas reduksi berisi fungsi konstan, pasangan string, dan fungsi di mana ukuran outputnya dapat mengikat setiap polinomial; maka adalah lengkap untuk wrt . $C$ $A$ $\mathsf{P}$ $C$

Kaveh
sumber

Untuk kelengkapan-P CVP di bawah FO-reduksi, lihat Latihan 3.28 di Kompleksitas Deskriptif Immerman .

András Salamon