Theory of Semi-Feasible Algorithms

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

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

This book presents a consolidated survey of the vibrant field of research known as the theory of semi-feasible algorithms. This research stream perfectly showcases the richness of, and contrasts between, the central notions of complexity: running time, nonuniform complexity, lowness, and NP-hardness. Research into semi-feasible computation has already developed a rich set of tools, yet is young enough to have an abundance of fresh, open issues.

Being essentially self-contained, the book requires neither great mathematical maturity nor an extensive background in computational complexity theory or in computer science in general. Newcomers are introduced to the field systematically and guided to the frontiers of current research. Researchers already active in the field will appreciate the book as a valuable source of reference.