Важко обчислити

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

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

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