The Computational Complexity of Equivalence and Isomorphism Problems

یک مدل محاسباتی چارچوبی برای انجام محاسبات بر اساس قوانین مشخص شده در برخی از داده های ورودی است. این مدل ها به عنوان مثال از نظریه اتوماتا، نظریه زبان رسمی، منطق یا نظریه مدار می آیند. قدرت محاسباتی چنین مدلی را می توان با ارزیابی مشکلات خاصی با توجه به آن مدل قضاوت کرد.
نظریه محاسبات مطالعه دشواری ذاتی مسائل محاسباتی، یعنی پیچیدگی محاسباتی آنهاست. این تک نگاری پیچیدگی محاسباتی مسائل رضایت‌پذیری، هم ارزی و تقریباً هم ارزی را با توجه به مدل‌های محاسباتی مختلف تحلیل می‌کند. به طور خاص، فرمول های بولی، مدارها و انواع مختلف برنامه های انشعاب در نظر گرفته می شوند.

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.