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

Основні поняття й означення теорії складності.Поняття поліноміального часу є центральною концепцією теорії складності обчислень.Навіть без урахування часової складності алгоритму, створити алгоритм для їх розв’язання неможливо.Наступним у ієрархії складності йде клас . Задачі класу можна розв’язати в поліноміальному просторі.Експоненційні алгоритми відповідають загальним поняттям про неефективні на практиці алгоритми.Рисунок 1 - Класи складності.Цей шифр є абсолютно надійним.Нагадаємо, що шифр Вернама (одноразового блокноту) був винайдений в 1917 році Гілбертом Вернамом.Ключем є будь-яке двійкове слово, однакової з довжини.Вона порівнює криптографічні методи та алгоритми і визначає їх надійність.