The Computational Complexity of Equivalence and Isomorphism Problems [electronic resource] / edited by Thomas Thierauf.

Contributor(s): Thierauf, Thomas [editor.] | SpringerLink (Online service)Material type: TextTextSeries: Lecture Notes in Computer Science ; 1852Publisher: Berlin, Heidelberg : Springer Berlin Heidelberg, 2000Description: VIII, 135 p. online resourceContent type: text Media type: computer Carrier type: online resourceISBN: 9783540453031Subject(s): Computer science | Computer Science | Computation by Abstract DevicesAdditional physical formats: Printed edition:: No titleDDC classification: 004.0151 LOC classification: QA75.5-76.95Online resources: Click here to access online
Contents:
Preliminaries -- Boolean Formulas and Circuits -- Branching Programs.
In: Springer eBooksSummary: 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.
Item type: E-BOOKS
Tags from this library: No tags from this library for this title. Log in to add tags.
    Average rating: 0.0 (0 votes)
Current library Home library Call number Materials specified URL Status Date due Barcode
IMSc Library
IMSc Library
Link to resource Available EBK5298

Preliminaries -- Boolean Formulas and Circuits -- Branching Programs.

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.

There are no comments on this title.

to post a comment.
The Institute of Mathematical Sciences, Chennai, India

Powered by Koha