The complexity of Graph Isomorphism (GI) is one of the major open problems. It is easy to see that . It is known that . The following theorem states that it is unlikely that GI is NP-complete. Theorem [Schöning'87, BHZ'87] : If GI is NP-complete then the polynomial hierarchy collapses to its second level. The counting [...]
Archive for September, 2010
Hardness of Graph Isomorphism
Posted in algorithms, complexity, graph theory, tagged determinant, graph isomorphism, LogCFL, NP-intermediate, perfect matching, polynomial hierarchy, strongly regular graphs on September 2, 2010 | 13 Comments »
Shiva Kintali
Search this Blog
-
-
Top Posts
-
Recent Posts
Categories
- algorithms (10)
- combinatorics (2)
- complexity (18)
- conferences (9)
- graph theory (13)
- mathematics (2)
- polyhedral combinatorics (3)
Archives
- May 2012 (4)
- March 2012 (1)
- February 2012 (1)
- November 2011 (2)
- September 2011 (2)
- July 2011 (1)
- June 2011 (1)
- March 2011 (1)
- February 2011 (1)
- November 2010 (2)
- September 2010 (1)
- July 2010 (1)
- June 2010 (1)
- February 2010 (2)
- January 2010 (1)
- November 2009 (1)
- October 2009 (1)
- September 2009 (3)
- August 2009 (1)
- July 2009 (3)
- June 2009 (3)
- May 2009 (2)
Kintali’s Twitter
- @lreyzin Congratulations. 1 day ago
- New blog post about one of my summer projects. kintali.wordpress.com/2012/05/28/tes… 2 days ago
- Please sign this petition. wwws.whitehouse.gov/petitions/!/pe… 1 week ago
- Please support my new word-building game (Tessel) on Kickstarter. kickstarter.com/projects/10725… 1 week ago
