The Graph Isomorphism Problem : Its Structural Complexity

By (author) Kobler, J.; By (author) Schoning, Uwe; By (author) Toran, Jacobo


  • Preliminaries.- 1 Decision Problems, Search Problems, and Counting Problems.- 1.1 NP-Completeness.- 1.1.1 The Classes P and NP.- 1.1.2 Reducibility.- 1.2 Reducing the Construction Problem to the Decision Problem.- 1.3 Counting versus Deciding for Graph Isomorphism.- 1.4 Uniqueness of the Solution.- 1.4.1 Random Reductions.- 1.4.2 Promise Problems.- 1.5 Reducing Multiple Questions to One.- 2 Quantifiers, Games, and Interactive Proofs.- 2.1 The Polynomial-Time Hierarchy.- 2.2 Interactive Proof Systems.- 2.2.1 The Class IP.- 2.2.2 Zero-Knowledge.- 2.3 Probabilistic Classes.- 2.3.1 Probability Amplification.- 2.3.2 The BP-Operator.- 2.3.3 Arthur-Merlin Games.- 2.4 Lowness and Collapses.- 3 Circuits and Sparse Sets.- 3.1 Polynomial Size Circuits.- 3.1.1 Circuits for NP.- 3.1.2 Circuits for Graph Isomorphism.- 3.2 Reductions to Sparse Sets.- 4 Counting Properties.- 4.1 Decision Reduces to Parity.- 4.2 Graph Isomorphism is Low for PP.- 4.3 The Reconstruction Conjecture.

「Nielsen BookData」より


書名 The Graph Isomorphism Problem : Its Structural Complexity
著作者等 Schoning, Uwe
Toran, Jacobo
Kobler, J.
書名別名 Its Structural Complexity
シリーズ名 Progress in Theoretical Computer Science
出版元 Springer-Verlag New York Inc.
刊行年月 2012.10.09
版表示 Softcover reprint of the original 1st ed. 1993
ページ数 167p
大きさ H280 x W210
ISBN 9781461267126
言語 英語
出版国 アメリカ合衆国