Bagaimana saya bisa menunjukkan masalah Gap-P di luar #P

14

Ada sejumlah masalah dalam teori representasi kombinatorial dan geometri aljabar yang tidak diketahui rumus positifnya. Ada beberapa contoh yang saya pikirkan, tetapi biarkan saya mengambil perhitungan koefisien Kronecker sebagai contoh saya. Biasanya, pengertian "formula positif" tidak didefinisikan secara tepat dalam kombinatorik, tetapi secara kasar berarti "deskripsi sebagai kardinalitas dari set yang tampaknya cukup eksplisit". Baru-baru ini, saya telah berbicara dengan Jonah Blasiak, dan dia telah meyakinkan saya bahwa definisi yang tepat dari "formula positif" adalah #P . Saya akan berasumsi bahwa, di situs ini, saya tidak perlu mendefinisikan #P.

Buergisser dan Ikenmeyer menunjukkan bahwa koefisien Kronecker adalah #P sulit. (Mereka juga selalu positif, karena mereka adalah multiplisitas produk tensor.) Tapi saya cukup yakin bahwa tidak ada yang tahu cara menghitung mereka yang bahkan membuat mereka menjadi #P.

Jadi, misalkan saya benar-benar berusaha membuktikan koefisien Kronecker tidak ada di #P. Saya berasumsi bahwa apa yang akan saya lakukan adalah mengasumsikan beberapa dugaan teori kompleksitas dan kemudian mengurangi produk Kronecker ke beberapa masalah lain yang diketahui lengkap untuk kelas yang lebih besar dari #P.

Dugaan apa yang mungkin saya asumsikan, dan masalah apa yang saya coba uraikan?

TAMBAH: Seperti yang telah ditunjukkan dalam komentar, Buergisser dan Ikenmeyer menunjukkan bahwa koefisien Kronecker ada di Gap-P, yang cukup dekat dengan #P. Jadi sepertinya pertanyaan-pertanyaan yang harus saya ajukan adalah (1) Apa saja masalah Gap-P-complete yang bisa saya kurangi secara masuk akal dan (2) bagaimana prospek menunjukkan bahwa Gap-P bukan #P? Saya kira (2) harus dibagi menjadi dua bagian (2a) apakah para ahli percaya kelas-kelas ini berbeda? dan (2b) apakah ada strategi untuk membuktikannya?

Saya harap banyak pengeditan pertanyaan ini tidak disukai.

cc.complexity-theory counting-complexity lower-bounds David E Speyer
sumber
5
Selamat datang di cerita! (Saya menambahkan kompleksitas penghitungan dan batas bawah pada pertanyaan).
Kaveh
3
@Kaveh Bürgisser dan Ikenmeyer menunjukkan bahwa menghitung koefisien Kronecker ada di GapP. David, apakah koefisien Kronecker selalu bilangan bulat non-negatif?
Tyson Williams
2
Iya. Mereka adalah multiplicites dari produk tensor, jadi mereka selalu tidak negatif.
David E Speyer
1
Anda memiliki masalah di GapP dan Anda ingin membuktikan bahwa itu di luar #P. Pendekatan yang jelas adalah untuk menunjukkan bahwa masalahnya adalah GapP-complete di bawah fungsional (Levin) reducibility, yang akan menyiratkan bahwa masalahnya ada di luar # P dengan asumsi # P ≠ GapP.
Tsuyoshi Ito
1
Apa yang saya tulis di komentar saya sebelumnya salah, karena setiap masalah di GapP dapat direduksi menjadi #P (jika saya tidak salah kali ini). Dengan kata lain, perbedaan antara #P dan GapP terlalu rumit untuk ditangani dengan menggunakan reducibilitas fungsional.
Tsuyoshi Ito

Jawaban:

12

Saya sarankan melihat properti fungsi #P yang berbeda dari fungsi Gap-P. Misalnya, menentukan apakah fungsi #P adalah nol dalam co-NP. Jika Anda dapat menunjukkan menentukan apakah koefisien Kronecker nol atau UP-hard maka Anda akan memiliki "Koefisien Kronecker di #P menyiratkan UP di co-NP", sebuah kesimpulan yang tidak mungkin.

Lance Fortnow
sumber
3

GapP adalah persis penutupan #P di bawah pengurangan. Di sisi lain, #P tidak ditutup dengan pengurangan kecuali UP = PP. Saya percaya itu menjawab pertanyaan Anda.

Tayfun Pay
sumber
4
Jika Anda menolaknya, setidaknya jelaskan mengapa itu salah .. Terima kasih
Tayfun Bayar
3
Saya setuju. Sejauh yang saya tahu jawabannya membuat dua pernyataan yang benar dan menjawab pertanyaan asli (meskipun pencarian saya mengungkapkan bahwa UP = PH adalah syarat yang diinginkan?)
Suresh Venkat
2
@ Suresh: Bagaimana posting ini menjawab pertanyaan awal? Pertanyaannya bukan tentang masalah lengkap GapP.
Tsuyoshi Ito
3
bagian (2) dalam pembaruan bertanya: "apa prospek GapP yang tidak sama dengan #P". jawaban ini menunjukkan bahwa kecuali terjadi keruntuhan, #P tidak ditutup dengan pengurangan sehingga tidak ada gunanya berbicara tentang kesetaraan.
Suresh Venkat
1
@ Suresh: Ini kertasnya. M.Ogiwara & L. Hemachandra. "Sebuah teori kompleksitas untuk sifat penutupan yang layak." Jurnal Ilmu Komputer dan Sistem Volume 46 Halaman 295-325. 1993.
Tayfun Bayar
0

Pertanyaan komputasi Karakter representasi tereduksi dari kelompok simetris mungkin menjadi kandidat alami.

Saya pikir Charles Hepler menunjukkan bahwa Gap-P lengkap, tetapi saya tidak yakin: untuk tautan ke tesis Masternya, lihat https://dspace.ucalgary.ca/handle/1880/45530?mode=full

Hari
sumber