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

Теорія складності обчислень
Тема вивчення/дослідження	квантова перевага і обчислювальна складність
Теорія складності обчислень у Вікісховищі

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

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

Огляд

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

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

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

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

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

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

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

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

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

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

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

Асимптотична складність

Позначення	Інтуїтивне пояснення	Визначення
$f(n)\in O(g(n))$	$f$ обмежена згори функцією $g$ (з точністю до постійного множника) асимптотично	$\exists (C>0),n_{0}:\forall (n>n_{0})\;|f(n)|\leq C|g(n)|$ або $\exists (C>0),n_{0}:\forall (n>n_{0})\;f(n)\leq Cg(n)$
$f(n)\in \Omega (g(n))$	$f$ обмежена знизу функцією $g$ (з точністю до постійного множника) асимптотично	$\exists (C>0),n_{0}:\forall (n>n_{0})\;|f(n)|\geq C|g(n)|$
$f(n)\in \Theta (g(n))$	$f$ обмежена знизу і згори функцією $g$ асимптотично	$\exists (C,C'>0),n_{0}:\forall (n>n_{0})\;C|g(n)|\leq |f(n)|\leq C'|g(n)|$
$f(n)\in o(g(n))$	$g$ домінує над $f$ асимптотично	$\forall (C>0)\exists n_{0}:\forall (n>n_{0})\;|f(n)|<C|g(n)|$
$f(n)\in \omega (g(n))$	$f$ домінує над $g$ асимптотично	$\forall (C>0)\exists n_{0}:\forall (n>n_{0})\;|f(n)|>C|g(n)|$
$f(n)\sim g(n)$	$f$ еквівалентна $g$ асимптотично	$\lim _{n\to \infty }{\frac {f(n)}{g(n)}}=1$

Поширені складності алгоритмів

Позначення	Пояснення	Приклади
$O(1)$	Сталий час роботи, незалежно від розміру задачі.	Очікуваний час пошуку в хеші.
$O(\log \log n)$	Дуже повільне зростання необхідного часу.	Очікуваний час роботи інтерполюючого пошуку $n$ елементів.
$O(\log n)$	Логарифмічне зростання — подвоєння розміру задачі збільшує час роботи на сталу величину.	Обчислення; двійковий пошук в масиві з $n$ елементів.
$O(n)$	Лінійне зростання — подвоєння розміру задачі подвоїть і необхідний час.	Додавання/віднімання чисел з $n$ цифр; лінійний пошук в масиві з $n$ елементів.
$O(n\cdot \log n)$	Лінеаритмічне зростання — подвоєння розміру задачі збільшить необхідний час трохи більше ніж вдвічі.	Сортування злиттям або купою $n$ елементів; нижня границя сортування порівнянням $n$ елементів.
$O(n^{2})$	Квадратичне зростання — подвоєння розміру задачі вчетверо збільшує необхідний час.	Елементарні алгоритми сортування.
$O(n^{3})$	Кубічне зростання — подвоєння розміру задачі збільшує необхідний час у вісім разів.	Звичайне множення матриць.
$O(c^{n})$	Експоненціальне зростання — збільшення розміру задачі на $1$ призводить до $c-$кратного збільшення необхідного часу; подвоєння розміру задачі підносить необхідний час у квадрат	Деякі задачі комівояжера, алгоритми пошуку повним перебором.

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

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

Клас P

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

Клас NP

Клас NP (від англ. non-deterministic polynomial) — множина задач розпізнавання, розв'язання яких є можливим за наявності деяких додаткових відомостей (так званого сертифіката рішення), тобто є можливість «швидко» (за час, що не перевершує полінома від розміру даних) перевірити розв'язок на машині Тьюрінга. Еквівалентно клас NP можна визначити як сукупність завдань, які можна «швидко» вирішити на недетермінованій машині Тьюрінга.

Клас складності NP визначається для множини мов, тобто множин слів над кінцевим алфавітом Σ. Мова L належить класу NP, якщо існують двомісний предикат $R(x,y)$ з класу P (тобто обчислюваний за поліноміальний час) і константа $C>0$ такі, що для будь-якого слова $x$ умова $x\in L$ рівносильна умові $\exists y,|y|<|y|$^$c$ $R(x,y)$.

Відношення класів складності NP та P

У теорії алгоритмів питання про рівність класів складності P і NP є однією з центральних відкритих проблем вже більше трьох десятиліть. Якщо на нього буде дана ствердна відповідь, це буде означати, що теоретично можливо вирішувати багато складних завдань істотно швидше, ніж зараз.
З визначення класів P і NP відразу випливає наслідок:$P\subseteq NP$ . Проте до цих пір нічого не відомо про суворість цього включення, тобто чи існує завдання, що лежить в NP, але не лежить в P. Якщо такого завдання не існує, то всі завдання, що належать класу NP, можна буде вирішувати за поліноміальний час, що обіцяє величезну вигоду з обчислювальної точки зору. Зараз найскладніші завдання з класу NP (так звані NP-повні задачі) можна вирішити за експоненційний час, що майже завжди неприйнятно.
В даний час більшість математиків вважають, що ці класи не рівні. Згідно з опитуванням, проведеним у 2002 році серед 100 вчених, 61 людина вважає, що відповідь — «не рівні»; 9 — «рівні»; 22 не змогли відповісти; 8 вважають, що гіпотеза не виводиться з поточної системи аксіом і, таким чином, не може бути доведена або спростована. З вищезазначеного видно, що проблема дослідження відношення класів P та NP є актуальною в науковому середовищі і потребує глибшого аналізу.

Непіддатливість

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

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

Важко обчислювати наприклад задачі складності NP і складніші, але й поліноміальні задачі теж бувають важкими. Це залежить від константи в асимптотичній оцінці складності. Наприклад задачу складності $o(n)$ ми завжди вважатимемо лінійною, навіть якщо константа біля $n$ буде дорівнювати $2^{500}$, але алгоритм з такою константою буде практично незастосовним.

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

Приклади

При порівнянні різних алгоритмів важливо знати, як їх складність залежить від обсягу вхідних даних. Припустимо, при сортуванні одним методом обробка тисячі чисел займає 1 с., А обробка мільйона чисел — 10 с., При використанні іншого алгоритму може знадобитися 2 с. і 5 с. відповідно. У таких умовах не можна однозначно сказати, який алгоритм краще.
У загальному випадку складність алгоритму можна оцінити по порядку величини. Алгоритм має складність $O(f(n))$, якщо при збільшенні розмірності вхідних даних $N$, час виконання алгоритму зростає з тією ж швидкістю, що і функція $f(N)$. Розглянемо код, який для матриці $A[NxN]$ знаходить максимальний елемент у кожному рядку.

Приклад:

 for i:=1 to N do
  begin
   max:=A[i,1];
   for j:=1 to N do
    begin
     if A[i,j]>max then
     max:=A[i,j]
    end;
   writeln(max);
 end;

У цьому алгоритмі змінна $i$ змінюється від $1$ до $N$. При кожній зміні $i$, змінна $j$ теж змінюється від $1$ до $N$. Під час кожної з $N$ ітерацій зовнішнього циклу, внутрішній цикл теж виконується $N$ раз. Загальна кількість ітерацій внутрішнього циклу дорівнює $N*N$. Це визначає складність алгоритму $O(N$^$2$$)$. Оцінюючи порядок складності алгоритму, необхідно використовувати тільки ту частину, яка зростає найшвидше. Припустимо, що робочий цикл описується виразом $N$^$3$$+N$. У такому разі його складність буде дорівнювати $O(N$^$3$$)$. Розгляд швидко зростаючої частини функції дозволяє оцінити поведінку алгоритму при збільшенні $N$. Наприклад, при $N=100$, то різниця між $N$^$3$$+N=1000100$ та $N=1000000$ дорівнює всього лише $100$, що становить $0,01\%$. При обчисленні $O$ можна не враховувати постійні множники у виразах. Алгоритм з робочим кроком $3*N$^$3$ розглядається, як $O(N$^$3$$)$. Це робить залежність ставлення $O(N)$ від зміни розміру задачі більш очевидною.

Найбільш складними частинами програми зазвичай є виконання циклів і виклик процедур. У попередньому прикладі весь алгоритм виконаний за допомогою двох циклів. Якщо одна процедура викликає іншу, то необхідно більш ретельно оцінити складність останньої. Якщо в ній виконується певне число інструкцій (наприклад, виведення на друк), то на оцінку складності це практично не впливає. Якщо ж викликана процедура виконується $O(N)$ кроків, то функція може значно ускладнити алгоритм. Якщо ж процедура викликається всередині циклу, то вплив може бути набагато більшим. До прикладу розглянемо дві процедури: Slow зі складністю $O(N$^$3$$)$ і Fast зі складністю $O(N$^$2$$)$.

Приклад:

 procedure Slow;
 var
 i,j,k: integer;
 begin
  for i:=1 to N do
   for j:=1 to N do
    for k:=1 to N do
    {будь-яка дія}
    end;
 procedure Fast;
 var
 i,j: integer;
 begin
  for i:=1 to N do
   for j:=1 to N do
   Slow;
 end;
 procedure Both;
 begin
  Fast;
 end;

Якщо у внутрішніх циклах процедури Fast відбувається виклик процедури Slow, то складності процедур перемножуються. У даному випадку складність алгоритму становить $O(N$^$2$$)*O(N$^$3$$)=O(N$^$5$$)$. Якщо ж основна програма викликає процедури по черзі, то їх складності додаються: $O(N$^$2$$)+O(N$^$3$$)=O(N$^$3$$)$. Наступний фрагмент має саме таку складність:

Приклад:

 procedure Slow;
 var
 i,j,k: integer;
 begin
  for i:=1 to N do
   for j:=1 to N do
    for k:=1 to N do
    {будь-яка дія}
 end;
 procedure Fast;
 var
 i,j: integer;
 begin
  for i:=1 to N do
   for j:=1 to N do
   {будь-яка дія}
 end;
 procedure Both;
 begin
  Fast;
  Slow;
 end;

Історія

Прикладом раннього аналізу складності алгоритмів є проведений аналіз алгоритму Евкліда, який зробив Габрієль Ламе 1844 року.

До початку досліджень, що були явно присвячені вивченню складності алгоритмів, багато дослідників заклали цьому теоретичний фундамент. Найвпливовішим серед них був Алан Тюрінг, що ввів поняття машин Тюрінга 1936 року, що виявилися дуже вдалими й гнучкими спрощеними моделями комп'ютера.

Див. також

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

Література

• 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 [Архівовано 20 березня 2021 у Wayback Machine.] (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)
• Кузюрін М. М., Фомін С. А. Ефективні алгоритми та складність обчислень. 2008
• Немирівський А. С., Юдін Д. Б. Складність і ефективність методів оптимізації. М.: Наука, 1979
• Ємець, В.; Мельник, А.; Попович, Р. (2003). Сучасна криптографія. Основні поняття (укр) . Львів: БаК. с. 69. ISBN 966-7065-44-8.

Посилання

• Complexity Zoo [Архівовано 27 серпня 2019 у Wayback Machine.] — «Зоопарк» класів складності.