Теорія складності обчислень

Теорія складності обчислень будучи підрозділом теоретичної інформатики займається дослідженням складності алгоритмів для розв'язання задач на основі формально визначених моделей обчислювальних пристроїв. Складність алгоритмів вимірюється за необхідними ресурсами, в основному, це тривалість обчислень або необхідний обсяг пам'яті. В окремих випадках досліджуються інші міри складності, такі як розмір мікросхем, або кількість процесорів необхідна для роботи паралельних алгоритмів.

Слід не плутати теорію складності обчислень з теорією обчислюваності, яка займається пошуком відповіді на запитання про те, які задачі можуть бути взагалі розв'язані із допомогою алгоритмів. Основна задача досліджень в теорії складності обчислень полягає у класифікації всіх розв'язних задач. Зокрема, робляться спроби відокремити множину задач з ефективними алгоритмами розв'язання від множини важко розв'язних задач.

Огляд

Обчислювальну складності алгоритму звичайно виражають через символ «О велике», що вказує порядок величини обчислювальної складності. Це просто член розкладання функції складності, що найшвидше зростає за умови зростання n; всі члени нищого порядку ігноруються. Наприклад, якщо часова складність порядку n², то вона виражається як O(n²).

Часова складність, виміряна подібним чином, не залежить від реалізації.

Не потрібно знати ні точного часу виконання окремих інструкцій, ні числа бітів, які являють різні змінні, ні навіть швидкості процесора. Один комп'ютер може бути на 50% швидший від іншого, а в третього ширина шини даних може бути вдвічі більше, проте складність алгоритму, що оцінена порядком величини, не зміниться. І це не є хитрим трюком. Під час оцінки доволі складних алгоритмів усім іншим можна знехтувати (з точністю до постійного множника).

Оцінка обчислювальної складності наочно демонструє, як об'єм вхідних даних впливає на вимоги до часу та об'єму пам'яті.

Наприклад, якщо T=O(n), подвоєння вхідних даних подвоїть і час виконання алгоритму. Якщо T=O(2ⁿ), додання лише одного біту до вхідних даних подвоїть час виконання алгоритму.

Головною ціллю теорії складності є забезпечення механізмів класифікації обчислювальних задач згідно з ресурсами, необхідних для їх розв'язання. Класифікація не має залежати від конкретної обчислювальної моделі, а скоріше оцінювати внутрішню складність задачі.

Ресурси, що оцінюються, як уже було зазначено раніше, можуть бути такими: час, простір пам'яті, випадкові біти, кількість процесорів, тощо, але зазвичай головним фактором є час, а іноді й простір.

Теорія розглядає мінімальний час і об'єм пам'яті для розв'язання найскладнішого варіанта задачі на теоретичному комп'ютері, відомому як машина Тюрінга. Машина Тюрінга є кінцевим автоматом з безкінечною магнітною стрічкою пам'яті для читання/запису. Це означає, що машина Тюрінга — реалістична обчислювальна модель.

Задачі, які можна розв'язати за допомогою алгоритмів з поліноміальним часом, називають такими, що можуть бути розв'язані, оскільки за умов нормальних вхідних даних вони можуть бути розв'язані за прийнятний час (точне визначення «прийнятності» залежить від конкретних умов).

Задачі, які можуть бути вирішені тільки за допомогою суперполіноміальних алгоритмів з поліноміальним часом, є обчислювально складними навіть за відносно малими значеннями n.

Алан Тюрінг довів, що деякі задачі неможливо розв'язати. Навіть без урахування часової складності алгоритму, створити алгоритм для їх розв'язання неможливо.

Класи складності

Задачі можна розбити на класи у відповідності зі складністю їх розв'язання. Клас P, що є найнижчим, містить усі задачі, які можна розв'язати за поліноміальний час. До класу NP входять усі задачі, які можна розв'язати за поліноміальний час тільки на недетермінованій машині Тюрінга (це варіант звичайної машини Тюрінга, що може робити припущення). Така машина робить припущення щодо розв'язку задачі — чи «вдачно вгадуючи», чи перебираючи усі припущення паралельно — та перевіряє своє припущення за поліноміальний час.

Посилання

• Використано матеріали зі статті в німецькій Вікіпедії

Див. також

• Список алгоритмів
• Обчислювальна складність
• Багатозначна зводимість
• PCP теорема

Ресурси інтернету

• Complexity Zoo — «Зоопарк» класів складності.

Література

• Christos H. Papadimitriou: Computational Complexity. Addison-Wesley, Reading/Mass. 1995, ISBN 0-201-53082-1.
• Lance Fortnow, Steve Homer: A Short History of Computational Complexity. Online-Manuskript (PDF, 225 kB)
• Jan van Leeuwen (Hrsg.): Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity. The MIT Press/Elsevier, Amsterdam 1994, ISBN 0-262-72020-5.
• Juris Hartmanis, Richard Edwin Stearns: On the computational complexity of algorithms. In: Trans. American Mathematical Society. 117/1965, S. 285–306, ISSN 0002-9947.
• Ding-Zhu Du, Ker-I Ko: Theory of Computational Complexity. John Wiley & Sons, New York 2000, ISBN 0-471-34506-7.
• Michael R. Garey, David S. Johnson: Computers and Intractability: A guide to the theory of NP-completeness. Freeman, New York 2003, ISBN 0-7167-1045-5.
• Michael Sipser: Introduction to the Theory of Computation. 2. Auflage. Thomson, Boston 2006, ISBN 0-534-95097-3. (International Edition)

Це незавершена стаття про комп'ютери. Ви можете допомогти проекту, виправивши або дописавши її.