Grafik “Tiny” Isomorphism

19

Sambil berpikir tentang kerumitan pengujian isomorfisme dari grafik asimetris (lihat pertanyaan terkait saya tentang teori), pertanyaan pelengkap muncul di benak saya.

Misalkan kita memiliki waktu polinomial mesin Turing M yang pada input 1n menghasilkan grafik GM,n dengan n node.

Kita dapat mendefinisikan masalah ΠM :

("Tiny" GI): Diberikan grafik G=(V,E) , adalah G isomorfik ke GM,|V|?

Dengan kata lain kita harus membandingkan grafik diberikan dengan "referensi" grafik dengan ukuran yang sama yang dihasilkan oleh waktu polinomial mesin Turing tetap M .

Untuk semua waktu polinomial Turing mesin M , kita memiliki ΠMNP , dan bagi banyak dari mereka kita memiliki ΠMP .
Tetapi apakah itu benar untuk semua M ? Apakah masalahnya diketahui?

Pada pandangan pertama, saya berpikir bahwa setiap ΠM harus lebih mudah daripada GI , karena untuk setiap n hanya ada satu "referensi" grafik ukuran itu dan mungkin simetri / asimetri dari grafik yang dihasilkan oleh M dapat dieksploitasi dan tester isomorfisma ad-hoc yang efisien dapat dibangun ... tetapi itu tidak benar: M dapat berisi beberapa jenis mesin Universal Turing berjangka waktu polinomial yang menggunakan input (unary) 1n untuk menghasilkan grafik referensi yang sama sekali berbeda (dalam struktur) seperti n meningkat.

Marzio De Biasi
sumber
Menarik, Tahukah Anda contoh mesin Turing P-time yang menghasilkan grafik G M , N ? MGM,N
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: Contoh sepele yang , adalah TM M yang hanya menghasilkan n simpul yang terisolasi (atau yang lain adalah TM yang menghasilkan K n ). Tanpa kehilangan sifat umum kita juga dapat memikirkan model di mana setiap kali polinomial TM atas alfabet biner menghasilkan grafik referensi: cukup pilih n 2 bit rekaman setelah berhenti, dan tafsirkan sebagai matriks kedekatan G M , n . ΠMPMnKnn2GM,n
Marzio De Biasi
Untuk TM yang menjamin bahwa G M , n memiliki siklus Hamiltonian, maka saya kira Π M tidak di P . MGM,nΠMP
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: Saya pikir itu tidak benar: cukup pilih TM yang hanya membangun siklus node: untuk semua n grafik referensi - yang memiliki siklus Hamilton - mudah diperiksa dalam waktu polinomial. Saya memiliki contoh non-sepele dari generator (agak sederhana) yang tampaknya sulit untuk menunjukkan bahwa masalahnya ada di P ; tapi saya ingin melakukan beberapa tes dengan nakal sebelum menambahkannya ke pertanyaan. nnP
Marzio De Biasi
1
Bagaimana dengan GI "Itsy Bitsy" di mana untuk M dan N yang tetap kita harus memutuskan apakah dua grafik yang dihasilkan pada 1 ^ n adalah sama? (Ini adalah bahasa unary.)
domotorp

Jawaban:

6

[Ini lebih dari beberapa komentar panjang daripada jawaban.]

1) Jika , maka tidak ada batasan polinom tetap pada kompleksitas waktu semua Π M , bahkan untuk M yang hanya membutuhkan waktu, katakanlah, n 3 : Jika untuk semua waktu- n 3 M , Π MD T I M E ( n k ) , maka berikut ini adalah algoritma poli-waktu untuk GI. Pada input ( G , H ) , membangun sebuah mesin Turing M G dengan jam yang memastikan bahwa M GGIPΠMMn3n3 MΠMDTIME(nk)(G,H)MGMGtidak pernah berjalan selama lebih dari langkah pada input ukuran n , dan sedemikian rupa sehingga M G ( 1 | V ( G ) | ) = G , dan kemudian menyelesaikan Π M G ( H ) dalam waktu O ( n k ) .n3nMG(1|V(G)|)=GΠMG(H)O(nk)

2) Karena untuk setiap , Π M tidak lebih sulit daripada GI, orang mungkin berpikir bahwa hasil terbaik di sepanjang baris " Π M tampaknya tidak berada di P " yang bisa diharapkan adalah hasil kelengkapan GI. Namun, tampaknya tidak mungkin bagi saya bahwa siapa pun ΠMΠMΠMP akan menjadi GI-lengkap, untuk setidaknya alasan berikut:ΠM

  • Semua hasil kelengkapan GI yang saya tahu adalah untuk kelas grafik yang agak besar, daripada memiliki grafik tunggal untuk setiap ukuran. Bahkan jika Anda drop persyaratan efisiensi seluruhnya, saya tidak tahu dari setiap daftar grafik sehingga | V ( G n ) | = n (atau bahkan p o l y ( n ) ) sehingga pengujian isomorfisme menjadi G n adalah lengkap-GI.G1,G2,|V(Gn)|=npoly(n)Gn

  • Pada catatan terkait, sebagian besar (semua?) Hasil kelengkapan GI tidak hanya banyak-satu reduksi, tetapi memiliki bentuk berikut: ada fungsi sehingga diberi instance ( G , H ) GI, ( f ( G) ) , f ( H ) ) adalah turunan dari masalah GI-complete lainnya. (Ini hanya morfisme poli-waktu dari hubungan ekivalensi, atau apa yang Fortnow dan saya sebut "reduksi kernel.) Kita dapat dengan mudah menunjukkan tanpa syarat bahwa tidak ada pengurangan dari GI ke sembarang Π M (bahkan jika Anda memodifikasi definisi untuk mengizinkan Mf(G,H)(f(G),f(H))ΠMM untuk menghasilkan beberapa grafik). Petunjuk: Dapatkan sebuah kontradiksi dengan menunjukkan bahwa apapun ituharus memiliki gambar sepenuhnya terkandung dalam { G M , n } n 0 .f{GM,n}n0

3) Meskipun seseorang dapat membuat berdasarkan pada TM universal seperti yang disarankan dalam pertanyaan, mungkin seseorang masih dapat membuat tester yang efisien, hanya saja tidak efisien. Yaitu, mungkin untuk setiap M , Π M ada dalam P / p o l y ?MMΠMP/poly

Joshua Grochow
sumber
1

Saya tidak punya jawaban untuk pertanyaan Anda, tetapi mengusulkan untuk mempertimbangkan versi yang lebih terbatas ΠM yang yang dapat kami tunjukkan bahwa itu terletak pada P.

Mari kita hanya mempertimbangkan kelompok grafik sedemikian rupa sehingga jumlah tepi tumbuh secara logaritmik. Saya akan memformalkan ini dengan mengulangi rumusan masalah Anda, juga untuk melihat apakah saya sudah memahaminya dengan benar.

Grafik tidak berarah dengan n tepi dapat digambarkan dengan n 2 - nGn bitstring panjang, cukup menggabungkan entri matriks adjacencyGdi segitiga atas. Karena itu ada2 n 2 - nn2n2G kemungkinan grafik padansimpul. Oleh karena itu setiap fungsif:NNsedemikian sehingga0f(n)<2n2-n2n2n2nf:NN untuk semuanmenggambarkan sekumpulan grafik. Untuk setiap fungsi yang dapat dihitung secara efisien sepertif,kami mendefinisikanΠfsebagai GΠf0f(n)<2n2n2nfΠf

GΠfG is isomorph to the graph described by f(|V(G)|)

For a natural number x let b1(x) be the number of 1's in its binary representation. Now, let us only consider Πf for efficiently computable functions f for which it holds that

b1(f(n))O(logn)
that is families of graphs for which the number of edges grows only logarithmically, as stated above.

We show that Πf for this class of functions is in P.

Let f be such a function and G be an input graph with n vertices. Let us call f(n) the reference graph. There are at most O(logn) edges in the reference graph. Thus every MCC(maximally connected component) can consist of at most O(logn) vertices of which there can be at most n. Note, that for any pair of graphs with only O(logn) vertices we can trivially check isomorphism in polynomialy time w.r.t. nkarena kita dapat mencoba semua permutasi. Dengan demikian menggunakan algoritma serakah untuk menetapkan setiap MCC dari grafik input MCC dalam grafik referensi kita dapat mengetahui apakah kedua grafik tersebut adalah isomorf.

John D.
sumber
If I understood well your f, if the number of edges grows only logarithmically w.r.t. n then it is easy to drop away the isolated vertices and test in polynomial time if G is isomorphic to the reference graph. So for this restricted class, ΠfP.
Marzio De Biasi
Indeed, it seems to be an easier argument than I thought. I will incorporate it in my answer.
John D.
Considering that the same argumentation works for GI in general this isn't really satisfying. I guess it would be interesting if one could improve the upper bound on the edges in the Πf setting such that it can't be shown analogously to work for GI in general anymore.
John D.
1
For the argument using brute force (all permutations in each component), I think you actually need each connected component to have at most O(logn/loglogn) vertices: (logn)! is essentially (logn)logn=nloglogn. However, using the best known GI algorithm which takes time 2vlogv, you can replace O(logn/loglogn) by O(log2n).
Joshua Grochow