Modified Branching Programs and Their Computational Power

برنامه‌های شاخه‌بندی، علاوه بر مدارهای بولی، مهم‌ترین مدل غیریکنواخت محاسبات هستند. این جلد به بررسی آخرین تحقیقات در این زمینه می پردازد. این یک رویکرد مبتنی بر برنامه منشعب به نظریه پیچیدگی ارائه می دهد. با شروع تعریفی از برنامه‌های انشعاب و بررسی تحقیقات قبلی، برنامه‌های انشعاب غیر قطعی معرفی و بررسی می‌شوند، بنابراین امکان شرح برخی از کلاس‌های پیچیدگی اساسی را فراهم می‌کنند. سپس کتاب بر مفهوم جدید برنامه‌های شاخه‌سازی امگا تمرکز می‌کند. جدا از تست‌های باینری معمولی، آن‌ها دارای ویژگی‌هایی برای ارزیابی توابع بولی اولیه هستند و برای توصیف کلاس‌های پیچیدگی محدود به فضا مناسب هستند. نویسنده با استفاده از این خصوصیات، جداسازی برخی از کلاس‌های پیچیدگی محدود را نشان می‌دهد. در ضمیمه تعدادی از مشکلات دسترسی به نمودار بسیار محدود ارائه شده است که به دلیل توضیحات برنامه انشعاب در فصل های 1-3، P-projection در کلاس های مورد بررسی کامل شده است.

Branching Programs are, besides Boolean circuits, the most important nonuniform model of computation. This volume gives a survey of the latest research in this field. It presents a branching program-based approach to complexity theory. Starting with a definition of branching programs and a review of the former research, nondeterministic branching programs are introduced and investigated, thus allowing the description of some fundamental complexity classes. The book then concentrates on the new concept of Omega-branching programs. Apart from the usual binary tests they contain features for evaluating certain elementary Boolean functions and are suited for characterizing space-bounded complexity classes. By means of these characterizations the author demonstrates the separation of some restricted complexity classes. In the appendix a number of extremely restricted graph-accessibility problems are given, which are, due to the branching program descriptions in chapters 1-3, p-projection complete in the classes under consideration.