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

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

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

Див. такожРедагувати

ПосиланняРедагувати

  • В. Ємець, А. Мельник, Р.Попович. Сучасна криптографія. Основні поняття. — БаК. — С. 69. — ISBN 966-7065-44-8.