The Computational Complexity of Equivalence and Isomorphism Problems

✍ Scribed by Thomas Thierauf (eds.)

Publisher: Springer-Verlag Berlin Heidelberg
Year: 2000
Tongue: English
Leaves: 143
Series: Lecture Notes in Computer Science 1852
Edition: 1
Category: Library

No coin nor oath required. For personal study only.

✦ Synopsis

A computational model is a framework for doing computations according to certain specified rules on some input data. These models come for example from automata theory, formal language theory, logic, or circuit theory. The computational power of such a model can be judged by evaluating certain problems with respect to that model.
The theory of computations is the study of the inherent difficulty of computational problems, that is, their computational complexity. This monograph analyzes the computational complexity of the satisfiability, equivalence, and almost-equivalence problems with respect to various computational models. In particular, Boolean formulas, circuits, and various kinds of branching programs are considered.

✦ Table of Contents

Introduction....Pages 1-10
Preliminaries....Pages 11-22
Boolean Formulas and Circuits....Pages 23-63
Branching Programs....Pages 65-120

✦ Subjects

Computation by Abstract Devices

📜 SIMILAR VOLUMES

The Computational Complexity of Equivale

📁 The Computational Complexity of Equivalence and Isomorphism Problems

✍ Thomas Thierauf (eds.) 📂 Library 📅 2000 🏛 Springer-Verlag Berlin Heidelberg 🌐 English

<p>A computational model is a framework for doing computations according to certain specified rules on some input data. These models come for example from automata theory, formal language theory, logic, or circuit theory. The computational power of such a model can be judged by evaluating certain pr

The Computational Complexity of Equivale

📁 The Computational Complexity of Equivalence and Isomorphism Problems (Lecture Notes in Computer Science, 1852)

✍ Thomas Thierauf 📂 Library 📅 2000 🏛 Springer 🌐 English

<span>A computational model is a framework for doing computations according to certain specified rules on some input data. These models come for example from automata theory, formal language theory, logic, or circuit theory. The computational power of such a model can be judged by evaluating certain

The Graph Isomorphism Problem: Its Struc

📁 The Graph Isomorphism Problem: Its Structural Complexity

✍ Johannes Köbler, Uwe Schöning, Jacobo Torán (auth.) 📂 Library 📅 1993 🏛 Birkhäuser Basel 🌐 English

<p>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 literatur

The Graph Isomorphism Problem: Its Struc

📁 The Graph Isomorphism Problem: Its Structural Complexity

✍ Koebler J., Schoening U., Toran J 📂 Library 📅 1993 🏛 Birkhäuser 🌐 English

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,

Complexity of structured computational p

📁 Complexity of structured computational problems

✍ Roberto Bevilacqua, et al. 📂 Library 📅 1991 🏛 Giardini 🌐 English

Computational Complexity of Algebraic an

📁 Computational Complexity of Algebraic and Numeric Problems

✍ Borodin, Allan; Munro, Ian 📂 Library 📅 1975 🏛 UMI Books on Demand;Elsevier Science Ltd 🌐 English