The computational complexity of equivalence and isomorphism problems [electronic resource] / Thomas Thierauf
- Author:
- Thierauf, Thomas
- Published:
- Berlin ; New York : Springer, [2000]
- Copyright Date:
- ©2000
- Physical Description:
- viii, 135 pages ; 24 cm.
- Access Online:
- serialssolutions.com
- Series:
- Lecture notes in computer science, 0302-9743 ; 1852
- Restrictions on Access:
- License restrictions may limit access.
- Contents:
- Machine generated contents note: 1.Introduction -- 1.1.Equivalence Problems -- 1.2.Isomorphism Problems -- 2.Preliminaries -- 2.1.Complexity Classes -- 2.2.Reductions -- 2.3.Probabilistic Complexity Classes -- 2.4.Probabilistic Quantifiers -- 2.5.Interactive Proofs -- 2.6.Isomorphisms and Other Transformations -- 3.Boolean Formulas and Circuits -- 3.1.An Interactive Proof for FNI -- 3.2.Comparing FI with Other Problems -- 4.Branching Programs -- 4.1.Read-k-Times Branching Programs -- 4.2.Polynomials -- 4.3.Ordered Branching Programs -- 4.4.Nondeterministic Branching Programs -- 4.5.Parity Branching Programs -- 4.6.Probabilistic Branching Programs.
- Subject(s):
- Genre(s):
- ISBN:
- 3540410325 (acid-free paper)
- Bibliography Note:
- Includes bibliographical references (pages [121]-130) and index.
View MARC record | catkey: 7805293