З поняттям алгоритму пов’язані такі поняття, як область його завдання, складність, еквівалентність, алгоритмічна розв’язність та ін.
Область завдання алгоритму — це множина даних, до яких алгоритм застосовний. Якщо алгоритм припиняється без результату або продовжується необмежено довго, то говорять про незастосовність алгоритму до цих вхідних даних.
Складність алгоритму — це величина, яка характеризує довжину опису алгоритму. А для оцінки складності обчислень, що виконуються в даному алгоритмі, використовується так звана сигналізуюча функція.
Під алгоритмічною розв’язністю масової проблеми розуміють можливість побудови алгоритму розв’язку всіх задач даного класу.
Існують класи задач, для розв’язання яких не існує одного універсального способу. Це алгоритмічно нерозв’язувані проблеми. Це не означає, що неможливо розв’язати окремі задачі даного класу. В кожному окремому випадку суттєво використовуються особливості вхідних даних, тобто порушується властивість масовості алгоритму. Для визначення алгоритмічного розв’язку якогось класу задач необхідно або побудувати алгоритм розв’язку, або довести неможливість побудови такого алгоритму, тобто довести, що проблема є алгоритмічно нерозв’язуваною.
Наприклад, алгоритмічно розв’язна проблема — доведення тотожностей в алгебрі (відомі правила перетворення алгебраїчних виразів), у той самий час розв’язання диференційних рівнянь — проблема алгоритмічно нерозв’язна. Є проблеми, про які невідомо, чи є вони алгоритмічно розв’язні чи нерозв’язні. Це свідчить про те, що на даний час вчені не в змозі побудувати алгоритм або довести неможливість його побудови, бо то є задачі одного рівня складності.
У практиці, однак, найчастіше буває так, що для будь-якого класу задач, для якого доведена неможливість існування алгоритму, який розв’язує всі задачі цього класу, завжди можна побудувати алгоритм, що розв’язує майже всі такі задачі. Термін «майже всі» використано в тому розумінні, що ймовірність зустріти на практиці конкретну задачу розглядуваного класу, що не розв’язується за допомогою побудованого алгоритму, достатньо мала.
