Apa bukti yang ada bahwa Graph Isomorphism tidak ada dalam ?

23

Termotivasi oleh komentar Fortnow pada posting saya, Bukti bahwa masalah Graph Isomorphism bukan -completeNP , dan oleh fakta bahwa adalah kandidat utama untuk -intermediate problem (bukan -complete atau ), saya tertarik pada bukti yang diketahui bahwa tidak dalam .GINPNPPGIP

Salah satu bukti tersebut adalah - dari masalah Automorfisme Grafik terbatas (masalah automorfisme grafik bebas titik-tetap adalah lengkap). Masalah ini dan generalisasi lainnya dipelajari dalam " Beberapa masalah NP-lengkap mirip dengan Graph Isomorphism " oleh Lubiw. Beberapa mungkin berpendapat sebagai bukti fakta bahwa meskipun lebih dari 45 tahun tidak ada yang menemukan algoritma waktu polinomial untuk .NPNPGIGI

Bukti apa lagi yang harus kita percaya bahwa tidak ada dalam ?GIP

Mohammad Al-Turkistany
sumber
2
Subgraph-isomorphism juga NP-complete.
1
Bukti yang agak lemah adalah kelas masalah yang berkembang yang setara dengan logspace dengan GI, namun tidak satupun yang tampaknya memiliki algoritma polytime yang jelas. (Tentu saja, jika salah satu dari mereka memang memiliki algoritma polytime maka mereka semua melakukannya.)
András Salamon
bukti mendalam yang mirip dengan P vs NP: dekade optimisasi algoritma GI misalnya bahari yang masih memiliki tren kasus terburuk non-P yang dapat diverifikasi secara eksperimental, tampaknya terutama pada grafik reguler acak.
vzn
Apa yang Anda pikirkan tentang ini? dharwadker.org/tevet/isomorphism
Anna Tomskova

Jawaban:

11

Sebelum pertanyaan ini, pendapat saya adalah bahwa Grafik Isomorfisme mungkin ada di P, yaitu bahwa tidak ada bukti untuk percaya bahwa GI tidak ada dalam P. Jadi saya bertanya pada diri sendiri apa yang akan dianggap sebagai bukti bagi saya: Jika ada algoritma dewasa untuk - grup isomorfisme yang sepenuhnya mengeksploitasi struktur -group yang tersedia dan masih tidak memiliki harapan untuk mencapai runtime polinomial, maka saya akan setuju bahwa GI mungkin tidak dalam P. Ada algoritma yang dikenal yang mengeksploitasi struktur yang tersedia seperti pengujian Isomorfisme untuk - kelompok. oleh O'Brien (1994)ppp, tapi saya belum membacanya secara cukup rinci untuk menilai apakah ia sepenuhnya mengeksploitasi struktur yang tersedia, atau apakah ada harapan untuk meningkatkan algoritma ini (tanpa mengeksploitasi struktur grup tambahan yang tidak jelas ) untuk mencapai runtime polinomial.p

Tetapi saya tahu bahwa Dick Lipton menyerukan tindakan menjelang akhir 2011 untuk mengklarifikasi kompleksitas komputasi dari masalah isomorfisma kelompok secara umum, dan tentang masalah kelompok isomorfisma secara khusus. Jadi saya mencari Googlep

site:https://rjlipton.wordpress.com group isomorphism

untuk melihat apakah seruan untuk bertindak telah berhasil. Itu memang:

  1. Masalah Isomorfisme Kelompok: Kemungkinan Masalah Polymath?
  2. Kemajuan Kelompok Isomorfisme
  3. Tiga Dari CCC: Kemajuan pada Isomorfisme Kelompok

Posting terakhir mengulas makalah yang mencapai runtime untuk keluarga penting kelompok tertentu, mengeksploitasi banyak struktur yang tersedia, dan mengakui makalah yang disebutkan di atas dari tahun 1994. Karena runtime terikat kompatibel dengan pengalaman bahwa grafik isomorfisma tidak sulit dalam praktiknya, dan dengan pengalaman bahwa tidak ada yang dapat menghasilkan algoritma waktu polinomial (bahkan untuk isomorfisme grup), ini dapat dihitung sebagai bukti bahwa GI tidak ada dalam P.nO(loglogn)nO(loglogn)

Thomas Klimpel
sumber
rjlipton.wordpress.com/2015/03/05/news-on-intermediate-masalah juga muncul oleh pencarian saya. Itu mengutip Teorema 2 Grafik Isomorfisma ada di . Selain itu, setiap masalah janji dalam milikRPMCSPSZKBPPMCSP as defined for promise problems. This is evidence that GI is not NP-complete, but this wasn't the question here. Let me add that I see no problem with the length or style of my answer, because I interpret a request for evidence as a request for a reasoned opinion.
Thomas Klimpel
5
I don't follow your reasoning. How can you know that the "available structure" is "fully exploited"? If anything, doesn't the Grochow-Qiao paper suggest that much more can be done with cohomology classes?
Sasho Nikolov
@SashoNikolov By the "available structure", I mean the knowledge about the structure in the group theory community, related communities and existing publications. Examples were the structure is not "fully exploited" are publications whose main goal is to come up with a practical implementable algorithm, which therefore stop at some point and just mention the remaining limitations without clear indications whether those are fundamental. The Grochow-Qiao paper reviewed those and directly attacked the computational complexity of group isomorphism, hence its results provide good evidence.
Thomas Klimpel
11

The smallest set of permutations you have to check to verify that no non-trivial permutations exist in a black box setting is better than n! but still exponential, OEIS A186202.

The number of bits needed to store an unlabeled graph is log2 of (n2)nlog(n)+O(n). See Naor, Moni. "Succinct representation of general unlabeled graphs." Discrete Applied Mathematics 28.3 (1990): 303-307. The compression method proof is a bit cleaner if I recall. Anyway, lets call that set U. Let L=2(n2) for labeled graphs.

--Haskell notation
graphCanonicalForm :: L -> U

graphIsomorphism :: L -> L -> Bool
graphIsomorphism a b = (graphCanonicalForm a) == (graphCanonicalForm b)    

UL and BoolLL if you convert to exponentials. Just examining their type signatures putting graphs in canonical form looks easier, but as shown above GC makes GI easy.

Chad Brewbaker
sumber
Thanks. How strong is this kind of arguments?
Mohammad Al-Turkistany
is there a ref to be cited that documents this connection further?
vzn
3
@MohammadAl-Turkistany: This is basically a query complexity argument. But known algorithms, e.g. Babai-Luks 1983, already beat this bound, I think by quite a significant margin (something like 2n versus 2n).
Joshua Grochow
1
@ChadBrewbaker: If your concern is being coded up, and average-case complexity I'm sure that nauty does significantly better than your algorithm. (Note that the best known lower bound on nauty is Ω(2n/20) (Miyazaki 1996), and a poly-time algorithm was found for the Miyazaki graphs. A simple analysis shows a lower bound of (3/2)n on your algorithm.) Also, GI is in average-case linear time (Babai-Kucera).
Joshua Grochow
2
@MohammadAl-Turkistany: this question has made me think more deeply about my beliefs on the complexity of GI. Re: your other question, note that if there is no poly-time Turing (or even many-one) reduction from GI to GA then PNP.
Joshua Grochow
8

Kozen in his paper, A clique problem equivalent to graph isomorphism, gives an evidence that GI is not in P. The following is from the paper:

"Nevertheless, it is likely that finding a polynomial time algorithm for graph isomorphism will be as difficult as finding a polynomial time algorithm for an NP-complete problem. In support of this claim, we give a problem equivalent to graph isomorphism, a small perturbation of which is NP-complete."

Also, Babai in his recent breakthrough paper Graph Isomorphism in quasipolynomial time gives an argument against the existence of efficient algorithms for GI. He observes that the group isomorphism problem (which is reducible to GI) is a major obstacle to placing GI in P. Group Isomorphism problem ( groups are given by their Cayley tableis) is solvable in nO(logn) and it is not known to be in P.

Here is an excerpt from Babai's paper:

The result of the present paper amplifies the significance of the Group Isomorphism problem (and the challenge problem stated) as a barrier to placing GI in P. It is quite possible that the intermediate status of GI (neither NP-complete, nor polynomial time) will persist.

Mohammad Al-Turkistany
sumber
2
From Kozen's Lem. 3 one can get a simpler example of this phenomenon: namely, Induced Subgraph Isomorphism (is H an induced subgraph of G) is exactly GI when |G|=|H|, but is NP-hard when |G|=c|H| for any c>1. For discrete parameters, we know there are problems in P that quickly become NP-complete (e.g. 2SAT vs 3SAT). Do you know if there are examples of problems in P with some continuous parameter that become NP-complete at a sharp threshold? If so, then this kind of reasoning wouldn't be much evidence that GI isn't in P, but I can't think of such an example off the top of my head.
Joshua Grochow
2
@JoshuaGrochow No, I am not aware of any such decision problems. But for optimization problems I know that finding an assignment satisfying 7/8 of the clauses is in P while finding an assignment satisfying 7/8+ϵ of the clauses is NP-hard even for satisfiable 3SAT formulas (ϵ>0 ).
Mohammad Al-Turkistany
Oops, Klimpel's answer already contains the group isomorphism evidence. Anyway, it is useful to have Babai's perspective on the matter.
Mohammad Al-Turkistany
Babai retracted the claim of quasipolynomial runtime. Apparently there was an error in the analysis.
Raphael
5

here are other results not cited yet

  • On the hardness of Graph Isomorphism / Torán FOCS 2000 and SIAM J. Comput. 33, 5 1093-1108.

    We show that the graph isomorphism problem is hard under DLOGTIME uniform AC0 many-one reductions for the complexity classes NL, PL (probabilistic logarithmic space) for every logarithmic space modular class ModkL and for the class DET of problems NC1 reducible to the determinant. These are the strongest known hardness results for the graph isomorphism problem and imply a randomized logarithmic space reduction from the perfect matching problem to graph isomorphism. We also investigate hardness results for the graph automorphism problem.

  • Graph Isomorphism is not AC0 reducible to Group Isomorphism / Chattopadhyay, Toran, Wagner

    We give a new upper bound for the Group and Quasigroup Isomorphism problems when the input structures are given explicitly by multiplication tables. We show that these problems can be computed by polynomial size nondeterministic circuits of unbounded fan-in with O(log log n) depth and O(log2 n) nondeterministic bits, where n is the number of group elements. This improves the existing upper bound from [Wol94] for the problems. In the previous upper bound the circuits have bounded fanin but depth O(log2 n) and also O(log2 n) nondeterministic bits. We then prove that the kind of circuits from our upper bound cannot compute the Parity function. Since Parity is AC0 reducible to Graph Isomorphism, this implies that Graph Isomorphism is strictly harder than Group or Quasigroup Isomorphism under the ordering defined by AC0 reductions.

vzn
sumber
4
Meskipun ini memang batas bawah terkuat yang diketahui pada GI, mereka tidak benar-benar mengatakan apa-apa tentang itu tidak berada dalam P. Dalam kasus pertama, DET tidak begitu dekat dengan P. Dalam kasus kedua, perhatikan bahwa struktur itu SEBUAHC0-degrees dalam P sudah cukup kaya.
Joshua Grochow
re "strongest known lower bounds on GI", ofc GI is in NP so an actual proof that GI is not in P is equivalent to P≠NP! (possibly via NPI≠∅)...
vzn
4
Yes, but, for example, it would be nice to know that GI is P-hard! (Of course, P-hardness has very little to do with showing that something is not in P, but it would at least suggest that GI is not in NC!)
Joshua Grochow