Контрольная работа: Основні поняття й ознаки теорії складності

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

Алгоритм, що на безкінечній послідовності входів робить більш ніж кроків, де n – довжина входу, а с > 0 – деяка константа, називається експоненційним .

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

Так, наприклад, реалізація ідеї несиметричного шифрування базується на понятті однобічної взаємно однозначної функції, такої, що при відомому порівняно просто обчислити , однак зворотню функцію обчислити (за прийнятний час) неможливо. Цю властивість називають практичною незворотністю. Зазвичай обчислення прямої функції має поліноміальну складність, а зворотної – у кращому випадку експоненційну. У криптосистемі RSA достатньо просто знайти добуток двох простих чисел (поліноміальна складність), але задача розкладання великого числа на прості співмножники є дуже складною (як мінімум експоненційної складності). Сьогодні не існує жодної однобічної функції, для якої математично була б доведена її практична незворотність або експоненційна складність. Ті функції, що знайшли довгострокове застосування в криптографії, вважаються однобічними. При цьому можна лише стверджувати, що на сьогодні відомі алгоритми обчислення зворотної функції зі складністю, що практично може бути реалізована (в рамках заданих параметрів).

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

Нехай f та g будуть двома такими функціями.

Запис f (n )= O ( g (n )) означає, що f асимптотично зростає не швидше, ніж g (n ), з точністю до постійного кратного, у той час як f (n )=(g (n )) означає, що f (n ) зростає, принаймні, також асимптотично швидко, як зростає g (n ), з точністю до постійного множника.

f(n ) =O (g (n )) означає, що функція f (n ) стає несуттєвою відносно g (n ) по мірі зростання n.

При цьому для будь-яких функцій f (n ), g (n ), h (n )і l (n ) справедливі такі властивості і співвідношення:

f (n )= O (g (n )), у випадку. якщо g (n ) = (f (n )).

f (n )=- (g (n )), у випадку. якщо f (n ) =O (g (n ))і(f )n =(g (n )).

Якщо f (n )= O (h (n ))і (g )n = O (h (n )), то( f + g )(n ) = O (h (n )).

Якщо f (n ) = O ( h (n ))і g (n ) = O (l (n )), то( f - g )( n) = O (h (n )l (n )).

Рефлексивність f (n ) = O (f (n )).

Транзитивність. Якщо f (n ) =O (g (n ))і g (n ) = O (h (n )), то f (n ) =O (h (n )).

Складність алгоритмів вимірюють кількістю арифметичних операцій (додавань, віднімань, множень і ділень із залишком), необхідних для виконання всіх дій. Однак це визначення не бере до уваги величини чисел, що беруть участь в обчисленнях. Тому, часто беруть до уваги ще й величину чисел, зводячи обчислення до бітових операцій, тобто оцінюючи кількість необхідних операцій із цифрами 0 і 1, у двійковому записі чисел. Це залежить від задачі, що розглядаються.

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