The Graph Isomorphism Problem Its Structural Complexity

The Graph Isomorphism Problem Its Structural Complexity / by J. Kobler, U. Schöning, J. Toran.

Recently, a variety ofresults on the complexitystatusofthegraph isomorphism problem has been obtained. These results belong to the so-called structural part of Complexity Theory. Our idea behind this book is to summarize such results which might otherwise not be easily accessible in the literature,...

Full description

Saved in:
Bibliographic Details
Main Authors: Kobler, J. (Author), Schöning, U. (Author), Toran, J. (Author)
Corporate Author: SpringerLink (Online service)
Format: eBook
Language:English
Published: Boston, MA : Birkhäuser Boston : Imprint: Birkhäuser, 1993.
Edition:1st ed. 1993.
Series:Progress in Theoretical Computer Science
Springer eBook Collection.
Subjects:
Computer science—Mathematics.
Applied mathematics.
Engineering mathematics.
Combinatorics.
Algorithms.
Computer mathematics.
Electronic resources (E-books)
Online Access:Click to view e-book
Holy Cross Note:Loaded electronically.
Electronic access restricted to members of the Holy Cross Community.
Table of Contents:
  • Preliminaries
  • 1 Decision Problems, Search Problems, and Counting Problems
  • 1.1 NP-Completeness
  • 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.5 Reducing Multiple Questions to One
  • 2 Quantifiers, Games, and Interactive Proofs
  • 2.1 The Polynomial-Time Hierarchy
  • 2.2 Interactive Proof Systems
  • 2.3 Probabilistic Classes
  • 2.4 Lowness and Collapses
  • 3 Circuits and Sparse Sets
  • 3.1 Polynomial Size Circuits
  • 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.

Similar Items