Apa algoritma yang paling efisien untuk memutuskan apakah suatu elemen adalah yang paling sedikit dalam orbitnya?

Diberikan grup bekerja pada himpunan dengan urutan total dan , algoritma apa yang paling efisien untuk memutuskan apakah x adalah elemen terkecil dalam orbitnya, dengan kata lain, memutuskan apakah ? $G$ $X$ $\leq$ $x\in X$ $min(Gx) = x$

Motivasi saya berasal dari pemecahan SMT di mana ada minat untuk secara otomatis memecahkan simetri. Menambahkan predikat melanggar simetri sering menghasilkan set klausa besar karena itu saya tertarik pada kemungkinan menangani ini sebagai propagasi teori malas.

Deskripsi di atas mungkin terlalu umum, dan seperti dicatat oleh sid , NP-hard. Tugas yang mungkin lebih sederhana adalah, diberikan sekelompok permutasi string panjang dikodekan sebagai seperangkat generator dan string panjang . Apa algoritma yang paling efisien untuk memutuskan apakah string itu adalah leksikografis terkecil di orbitnya? $n$ $x$ $n$

ds.algorithms gr.group-theory HaskellElephant
sumber

Saya kira Anda berbicara tentang himpunan terbatas X? Saya pikir memutuskan ini NP-hard. Biarkan

menjadi tur dari serangkaian kota dalam masalah Salesman Perjalanan dengan

. Biarkan grup

menjadi grup simetris

. Maka orbitnya adalah semua kemungkinan tur dan membuktikan bahwa salah satunya adalah minimum NP-hard.

X = {c_{1}, \dots, c_{n}}

$X=\{c_1,\dots,c_n\}$

c_{1} \to c_{2} \dots

$c_1 \rightarrow c_2 \dots$

G

$G$

S_{n}

$S_n$

Pilih

@ Id, ya saya hanya tertarik pada kasus di mana X adalah terbatas, dan saya belum memikirkannya tapi itu pasti NP-hard. Saya kira mungkin masih ada kemungkinan algoritma monte carlo yang efisien.

HaskellElephant

Meskipun jika Anda menggunakan kriteria yang berbeda untuk minimum, itu jumlahnya banyak di sini: mudah untuk menemukan tur terkecil secara leksikografis (setidaknya jika Anda menganggap semua tepi memiliki label yang berbeda; jika tidak, itu masih NP-hard).

Peter Shor

@ PeterShor, ya, sebenarnya untuk tujuan saya, segala bentuk kanonik akan dilakukan.

HaskellElephant

Jika

dan

disajikan sebagai firman nilai, ini membutuhkan pencacahan

G

$G$

X

$X$

G

$G$

David Harris

Jawaban:

Untuk hubungan kesetaraan umum, bukan yang muncul dari aksi grup permutasi, bahkan menemukan leksikografis paling tidak masih "terlalu" umum. Menemukan elemen terkecil secara leksikografis dalam kelas ekivalensi dapat berupa -hard (pada kenyataannya, -hard) - bahkan jika hubungannya memiliki bentuk kanonik waktu polinomial [1]. $NP$ $P^{NP}$

Namun, untuk masalah orbit kelompok permutasi seperti yang Anda gambarkan, memutuskan apakah dua titik terletak pada orbit yang sama tidak mungkin menjadi -hard: berada dalam , dan karenanya bukan -hard kecuali jika hierarki polinomial runtuh ke tingkat kedua. $NP$ $NP \cap coAM$ $NP$

$2^{\tilde{O}(\sqrt{n})}$

$P$ $P$ $NP = UP = RP$ $BPP$ $P$ , tetapi hasil ini menunjukkan bahwa meskipun terletak pada kelas kompleksitas yang lebih tinggi masalah sulit lainnya mungkin masih menghalangi Anda.

Jadi saya pikir jika Anda ingin beberapa batas atas yang lebih baik Anda benar-benar membutuhkan masalah untuk lebih spesifik.

[1] Andreas Blass dan Yuri Gurevich. Hubungan ekivalensi, invarian, dan bentuk normal . SIAM J. Comput. 13: 4 (1984), 24-42.

[2] László Babai dan Eugene M. Luks. Pelabelan kanonik dari grafik . STOC 1983, 171-183.

[3] Lance Fortnow dan Joshua A. Grochow. Kelas kompleksitas masalah kesetaraan ditinjau kembali . Memberitahu. dan Komputasi. 209: 4 (2011), 748-763. Juga tersedia sebagai arXiv: 0907.4775v2 .

Joshua Grochow
sumber

P E q = C F

$PEq=CF$

Tidak sejauh yang saya tahu. Paling-paling itu akan menyiratkan bahwa masalah isomorfisma kombinatorial ada di Ker (FP); satu masalah adalah bahwa bentuk kanonik untuk grafik tidak perlu menghasilkan bentuk kanonik untuk struktur yang Anda mulai; masalah lainnya adalah bahwa isomorfisma kombinatorial belum tentu PEq-lengkap. Kami bertanya apakah ada masalah PEq-complete; Finkelstein dan Hescott menunjukkan masalah CEq-lengkap untuk C lebih tinggi di PH, tetapi dibiarkan terbuka pertanyaan tentang keberadaan masalah PEq-lengkap.

Joshua Grochow

mungkinkah keberadaan masalah lengkap dalam PEq menyiratkan PH runtuh ke tingkat tertentu?

T ....

@ Turbo: Tentu, meskipun sepertinya agak tidak mungkin bagi saya. Apakah Anda tahu ada contoh di mana keberadaan masalah lengkap untuk beberapa kelas menyiratkan PH runtuh? (Selain masalah PH-lengkap.) Saya pikir kemungkinan ada (a) Masalah PEq-lengkap ada (dan tidak bertentangan dengan dugaan besar), kami hanya belum menemukan cara untuk membangunnya, atau (b) ada adalah oracle berjalan dua arah tentang keberadaan masalah PEq-lengkap. (B) tampaknya lebih mungkin bagi saya - dengan analogi dengan BPP - karena PEq pada dasarnya adalah kelas semantik.

Joshua Grochow