|
|
|
|
| LEADER |
01617nam a2200253 a 4500 |
| 001 |
1575739 |
| 005 |
20171111233701.0 |
| 008 |
960614s1993 cy da er 000 u eng d |
| 020 |
|
|
|a 0817636803
|q (U.S.)
|q hbk.
|
| 020 |
|
|
|a 3764336803
|q (Germany)
|
| 040 |
|
|
|a CY
|b University of Cyprus
|e AACR-2
|q hbk.
|
| 050 |
|
|
|a QA267.7.K63 1993
|
| 100 |
1 |
|
|a Kobler, Johannes,
|d 1958-
|
| 245 |
1 |
4 |
|a The graph isomorphism problem:
|b its structural complexity/
|c Johannes Kobler, Uwe Schoning, Jacobo Toran
|
| 260 |
|
|
|a Boston:
|b Birkhauser,
|c c1993
|
| 300 |
|
|
|a 160 p. :
|b ill. ;
|c 25 cm.
|
| 490 |
0 |
|
|a Progress in theoretical computer science
|
| 500 |
|
|
|a Includes bibliographical references (p. [149]-157) and index.
|
| 500 |
|
|
|a Contents: 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.
|
| 650 |
|
0 |
|a Computational complexity
|
| 650 |
|
0 |
|a Graph theory
|x Data processing
|
| 700 |
1 |
|
|a Schoning, Uwe,
|
| 700 |
1 |
|
|a Toran, Jacobo,
|
| 952 |
|
|
|a CY-NiOUC
|b 5a0435766c5ad14ac1e9468c
|c 998a
|d 945l
|e QA267.7.K63 1993
|t 1
|x m
|z Books
|
