000 02341nam a22004455i 4500
001 978-3-540-45303-1
003 DE-He213
005 20160624102000.0
007 cr nn 008mamaa
008 121227s2000 gw | s |||| 0|eng d
020 _a9783540453031
_9978-3-540-45303-1
024 7 _a10.1007/3-540-45303-2
_2doi
050 4 _aQA75.5-76.95
072 7 _aUYZG
_2bicssc
072 7 _aCOM037000
_2bisacsh
082 0 4 _a004.0151
_223
245 1 4 _aThe Computational Complexity of Equivalence and Isomorphism Problems
_h[electronic resource] /
_cedited by Thomas Thierauf.
260 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg,
_c2000.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg,
_c2000.
300 _aVIII, 135 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aLecture Notes in Computer Science,
_x0302-9743 ;
_v1852
505 0 _aPreliminaries -- Boolean Formulas and Circuits -- Branching Programs.
520 _aA 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.
650 0 _aComputer science.
650 1 4 _aComputer Science.
650 2 4 _aComputation by Abstract Devices.
700 1 _aThierauf, Thomas.
_eeditor.
710 2 _aSpringerLink (Online service)
773 0 _tSpringer eBooks
776 0 8 _iPrinted edition:
_z9783540410324
786 _dSpringer
830 0 _aLecture Notes in Computer Science,
_x0302-9743 ;
_v1852
856 4 0 _uhttp://dx.doi.org/10.1007/3-540-45303-2
942 _2EBK5298
_cEBK
999 _c34592
_d34592