Pembagian oleh dua fungsi di #P

Biarkan menjadi fungsi bernilai integer sehingga ada di . Apakah itu berarti ada di ? Adakah alasan untuk meyakini hal ini tidak mungkin selalu berlaku? Adakah referensi yang harus saya ketahui? $F$ $2F$ $\#P$ $F$ $\#P$

Agak mengherankan, situasi ini muncul (dengan konstanta yang jauh lebih besar), untuk fungsi yang mana adalah masalah terbuka lama. $F$ $F \in? \#P$

Catatan: Saya menyadari makalah M. Ogiwara, L. Hemachandra, Sebuah teori kompleksitas untuk sifat penutupan yang layak di mana masalah pembagian-by-2 terkait telah dipelajari (lihat Thm 3.13). Namun masalah mereka berbeda, karena mereka mendefinisikan divisi untuk semua fungsi melalui operator lantai. Itu memungkinkan mereka melakukan pengurangan cepat terhadap masalah paritas.

cc.complexity-theory complexity-classes counting-complexity Igor Pak
sumber

@ Kaveh: Jika adalah fungsi , dan fungsi waktu-poli, maka ada di , tetapi belum tentu (agaknya). Sebagai contoh, tampaknya tidak ada alasan mengapa semua fungsi GapP nonnegatif harus di , tetapi mereka dapat direduksi menjadi dengan cara ini.

f (x)

$f(x)$

# P

$\#P$

g (y)

$g(y)$

f (g (y))

$f(g(y))$

# P

$\#P$

g (f (x))

$g(f(x))$

# P

$\#P$

# P

$\#P$

Emil Jeřábek mendukung Monica

@ JoshuaGrochow: Ya, ini "Terima jika dan hanya jika Anda menebak kedua saksi 2F dalam urutan leksikografis".

@ JoshuaGrochow Jika Anda melakukan pembagian tanpa fungsi lantai maka

runtuh ke kelas kompleksitas berikut, yang baru saja saya definisikan, melalui Teorema 5.9 pada buku TCTC.

ada predikat polinomial waktu P dan q polinomial sehingga, untuk semua

P P

${\bf PP}$

U P P X = {L |

${\bf UPPX} = \{ L |$

x

$x$

1.

$\bf 1.$

x \notin L \Rightarrow | | {y |

$x \not \in L \Rightarrow ||\{y|$

Kemudian salah satu kebutuhan untuk menunjukkan di mana

termasuk dalam hirarki kompleksitas. Mudah-mudahan kasusnya adalah

| y | \leq q (| x |) \land P (x, y)} | | < 1

$|y|\leq q(|x|) \wedge P(x,y)\}|| < 1$

2.

$\bf 2.$

x \in L \Rightarrow | | {y |

$x \in L \Rightarrow ||\{y|$

| y | \leq q (| x |) \land P (x, y)} | | \geq 1

$|y|\leq q(|x|) \wedge P(x,y)\}|| \geq 1$

}

$\}$

U P P X

${\bf UPPX}$

U P P X = P P

${\bf UPPX} = {\bf PP}$

Tayfun Pay

Seberapa sulit untuk mengetahui apakah fungsi di #PP selalu sama? Saya berharap itu tidak dapat dipastikan.

Peter Shor

@PeterShor: Itu tentu tidak bisa dipastikan. Satu dapat mengambil mesin yang menerima jika dan hanya jika saksi penghitungan adalah semua 1s dan panjang yang sama dengan input dan M berhenti persis langkah [panjang itu].

Jawaban:

Saya mencoba memberikan intuisi saya mengapa saya pikir ini tidak mungkin berlaku. Ambil masalah favorit Anda di , dan ubah menjadi masalah di , misalnya, fungsi kami dapat menjadi jumlah siklus Hamiltonian dalam input 3-grafik biasa yang mengandung batas tetap tertentu. Dari argumen paritas kita tahu bahwa selalu bahkan, sehingga Anda dapat menentukan dan saya tidak melihat alasan mengapa akan di . $PPA$ $\sharp P$ $f$ $f$ $F:=f/2$ $F$ $\sharp P$

domotorp
sumber

Baik. Sekarang aku bingung. Bukankah

memiliki tiga siklus Hamilton?

K_{4}

$K_4$

Peter Shor

Oke ... saya sudah memeriksanya. Teorema adalah bahwa setiap sisi muncul dalam jumlah siklus Hamiltonian genap (tidak terarah) dalam grafik 3-reguler, bukan bahwa ada jumlah total siklus Hamiltonian genap. Jadi masalah penghitungan yang benar adalah: diberi grafik tiga-reguler dan tepi

, misalkan

adalah jumlah siklus Hamiltonian dalam

yang melewati

. Apakah

di #P?

e

$e$

f

$f$

G

$G$

e

$e$

F / 2

$F/2$

Peter Shor

Memang, lucu bahwa tidak ada yang memperhatikan sebelumnya ... Saya sudah menambahkannya.

domotorp

Meskipun secara umum saya setuju dengan intuisi Anda, dalam hal ini, saya pikir

sebenarnya ada di #P: Biarkan e = (v_1, v_2) menjadi ujung dalam G. Biarkan u, w menjadi tetangga dari v_1 yang tidak t v_2. Mesin NP berikut memiliki jalur penerimaan f / 2: tebak siklus Hamilton yang mencakup sepasang tepi (u, v_1) dan (v_1, v_2). (Intinya adalah bahwa bukti kesamaan paritas menciptakan sebuah penipisan antara siklus Ham seperti itu dan yang termasuk (w, v_1) dan (v_1, v_2).) Jadi untuk intuisi untuk bekerja, Anda memerlukan sesuatu dalam PPA yang melalui eg sebuah argumen penghitungan, atau yang menghindari

f / 2

$f/2$

penipisan yang

Faktanya tidak benar. Misalnya, mudah untuk memeriksa apakah ia gagal untuk semua grafik 3-reguler yang terhubung pada 8 simpul (lihat en.wikipedia.org/wiki/Table_of_simple_cubic_graphs#8_nodes untuk daftar), kecuali untuk kubus (yang merupakan transitif tepi) .

Emil Jeřábek mendukung Monica