Основи теорії обчислювальної складності EITC/IS/CCTF

Оскільки кількість ресурсів, необхідних для виконання алгоритму, змінюється залежно від розміру вхідних даних, складність зазвичай виражається як функція f(n), де n — розмір вхідних даних, а f(n) — складність у найгіршому випадку ( максимальна кількість ресурсів, необхідна для всіх входів розміру n) або середня складність випадку (середня кількість ресурсів для всіх входів розміру n). Кількість необхідних елементарних операцій на вході розміру n зазвичай визначається як тимчасова складність, коли вважається, що елементарні операції займають постійну кількість часу на конкретному комп’ютері і змінюються лише на постійний коефіцієнт під час виконання на іншій машині. Обсяг пам'яті, необхідний алгоритму на вході розміру n, відомий як складність простору.

Час є найбільш поширеним ресурсом. Коли термін «складність» використовується без уточнювача, він зазвичай відноситься до складності часу.

Традиційні одиниці часу (секунди, хвилини тощо) не використовуються в теорії складності, оскільки вони занадто залежать від обраного комп’ютера та розвитку технологій. Наприклад, сьогодні комп’ютер може виконувати алгоритм значно швидше, ніж комп’ютер 1960-х років, але це пов’язано радше з технологічними проривами в комп’ютерному обладнанні, а не з властивою якістю алгоритму. Метою теорії складності є кількісна оцінка потреб у часі, властивих алгоритмам, або фундаментальних обмежень часу, які алгоритм накладає на будь-який комп’ютер. Це досягається шляхом підрахунку, скільки основних операцій виконується під час обчислення. Ці процедури зазвичай називають кроками, оскільки вважають, що вони займають постійний час на певній машині (тобто на них не впливає кількість введених даних).

Іншим важливим ресурсом є обсяг пам'яті комп'ютера, необхідний для виконання алгоритмів.

Ще одним часто використовуваним ресурсом є кількість арифметичних дій. У цьому сценарії використовується термін «арифметична складність». Часова складність, як правило, є добутком арифметичної складності на постійний коефіцієнт, якщо відоме верхнє обмеження на розмір двійкового представлення чисел, які виникають під час обчислення.

Розмір цілих чисел, які використовуються під час обчислення, не обмежений для багатьох методів, і нереально припустити, що арифметичні операції потребують фіксованого часу. В результаті тимчасова складність, також відома як бітова складність, може бути значно вищою за складність арифметики. Наприклад, арифметична складність обчислення визначника цілочисельної матриці nn становить O(n^3) для стандартних методів (виключення по Гауссу). Оскільки під час обчислення розмір коефіцієнтів може експоненціально збільшуватися, бітова складність тих самих методів експоненціальна в n. Якщо ці методи використовуються в поєднанні з багатомодульною арифметикою, бітова складність може бути зменшена до O(n^4).

Бітова складність, формально, відноситься до кількості операцій над бітами, необхідних для виконання алгоритму. У більшості обчислювальних парадигм він дорівнює тимчасовій складності до постійного коефіцієнта. Кількість операцій над машинними словами, необхідних комп’ютерам, пропорційна бітовій складності. Таким чином, для реалістичних моделей обчислень часова складність і бітова складність ідентичні.

Ресурсом, який часто враховується при сортуванні та пошуку, є кількість порівнянь записів. Якщо дані добре впорядковані, це є хорошим показником складності часу.

На всіх потенційних входах підрахувати кількість кроків в алгоритмі неможливо. Оскільки складність входу зростає з його розміром, його зазвичай представляють як функцію розміру входу n (у бітах), і тому складність є функцією від n. Однак для вхідних даних однакового розміру складність алгоритму може істотно відрізнятися. В результаті регулярно використовуються різноманітні функції складності.

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

Найгірший і середній випадок складності, як відомо, важко правильно обчислити. Більше того, ці точні значення мають мало практичного застосування, оскільки будь-яка зміна в машині чи парадигмі обчислень дещо змінить складність. Крім того, використання ресурсів не є важливим для малих значень n, тому простота реалізації часто більш приваблива, ніж низька складність для малих n.

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

Обчислювальні моделі

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

Детермінована модель обчислень — це модель, в якій наступні стани машини та операції, які мають виконуватися, повністю визначаються попереднім станом. Рекурсивні функції, лямбда-числення та машини Тьюринга були першими детермінованими моделями. Машини з довільним доступом (також відомі як RAM-машини) є популярною парадигмою для моделювання реальних комп’ютерів.

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

Різні варіанти можуть бути зроблені на деяких етапах обчислення в недетермінованій моделі обчислень, наприклад, недетерміновані машини Тьюринга. У теорії складності всі можливі варіанти розглядаються одночасно, а недетермінована часова складність — це кількість часу, необхідного, коли завжди робиться найкращий вибір. Іншими словами, обчислення виконуються одночасно на стільки (ідентичних) процесорах, скільки потрібно, а недетермінований час обчислення — це час, який перший процесор потребує для завершення обчислень. Цей паралелізм можна використовувати в квантових обчисленнях, використовуючи накладені заплутані стани під час виконання спеціалізованих квантових алгоритмів, таких як, наприклад, розкладання крихітних цілих чисел за Шором.

Навіть якщо така обчислювальна модель наразі неможлива, вона має теоретичне значення, зокрема щодо проблеми P = NP, яка запитує, чи класи складності, створені з використанням «поліноміального часу» та «недетермінованого поліноміального часу» як найменшого верхнього рівня межі однакові. На детермінованих комп’ютерах моделювання NP-алгоритму вимагає «експоненціального часу». Якщо задачу можна розв’язати за поліноміальний час на недетермінованій системі, вона належить до класу складності NP. Якщо проблема знаходиться в NP і не є легшою, ніж будь-яка інша задача NP, вона називається NP-повною. Задача про рюкзака, проблема комівояжера та булева задача на виконання — все це NP-повні комбінаторні задачі. Найвідоміший алгоритм має експоненційну складність для всіх цих задач. Якби будь-яку з цих задач можна було розв’язати за поліноміальний час на детермінованій машині, то всі проблеми NP можна було б вирішити також за поліноміальний час, і P = NP було б встановлено. Станом на 2017 рік широко припускається, що P NP, що означає, що найгірші ситуації проблем NP принципово важко розв’язувати, тобто займають набагато більше часу, ніж будь-який можливий проміжок часу (десятиліття) з урахуванням цікавих вхідних довжин.

Паралельні та розподілені обчислення

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

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

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

Квантові обчислення

Квантовий комп'ютер - це комп'ютер з моделлю обчислень, заснованої на квантовій механіці. Теза Черча-Тюрінга справедлива для квантових комп’ютерів, маючи на увазі, що будь-яка проблема, яку може вирішити квантовий комп’ютер, також може бути вирішена машиною Тьюринга. Проте теоретично деякі задачі можна було б вирішити за допомогою квантового комп’ютера, а не класичного комп’ютера зі значно меншою часовою складністю. Поки що це суто теоретично, оскільки ніхто не знає, як розробити практичний квантовий комп’ютер.

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

Складність задачі (нижні межі)

Мінімумом складності алгоритмів, які можуть вирішити проблему, включаючи невідкриті методи, є складність проблеми. В результаті складність проблеми дорівнює складності будь-якого алгоритму, який її розв’язує.

В результаті будь-яка складність, наведена у великій нотації O, представляє складність як алгоритму, так і супутньої проблеми.

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

Щоб вирішити більшість проблем, необхідно прочитати всі вхідні дані, що займає час, пропорційний величині даних. В результаті такі задачі мають принаймні лінійну складність, або, у великих омегах, складність Ω(n).

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

Кількість порівнянь, необхідних для алгоритму сортування, має нелінійну нижню межу Ω(nlogn). В результаті найкращі алгоритми сортування є найефективнішими, оскільки їх складність O(nlogn). Справа в тому, що є н! Способи організації n речей веде до цієї нижньої межі. Тому що кожне порівняння розділяє цю колекцію n! порядків на дві частини, кількість N порівнянь, необхідних для розрізнення всіх порядків, має бути 2N > n!, що означає O(nlogn) за формулою Стірлінга.

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

Розробка алгоритму

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

Часто буває непорозумінням, що в результаті закону Мура, який передбачає експоненційне зростання потужності сучасних комп’ютерів, оцінка складності алгоритмів стане менш актуальною. Це неправильно, оскільки підвищена потужність дозволяє обробляти величезні обсяги даних (великі дані). Наприклад, будь-який алгоритм повинен добре функціонувати менше ніж за секунду при сортуванні в алфавітному порядку списку з кількох сотень записів, наприклад бібліографії книги. З іншого боку, для мільйона записів (наприклад, номерів телефонів великого міста) основні алгоритми, які вимагають порівнянь O(n2), мали б виконати трильйон порівнянь, що зайняло б три години зі швидкістю 10 мільйонів порівнянь за секунду. Швидке сортування та сортування злиттям, з іншого боку, вимагають лише порівняння nlogn (як середня складність для першого, як складність найгіршого випадку для останнього). Це дає близько 30,000,000 1,000,000 3 порівнянь для n = 10 XNUMX XNUMX, що займе лише XNUMX секунди при XNUMX мільйонах порівнянь в секунду.

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