1.3. Перетворення (зводимість) задач
Означення 1.6 Задача A може бути перетворена в задачу B (задача А зводиться до задачі В), якщо:
- Вхідні дані задачі А перетворюються у вхідні дані задачі В.
- Розв'язується задача В.
- Результат розв'язку задачі В перетворюється у правильний розв'язок задачі А.
Якщо кроки 1 та 3 можна виконати за час O(r(N)), де N - розмір задачі A, то кажуть, що задача А є r(N) звідною до В і позначають так: 
. Звідність не є симетричним відношенням. Якщо задачі А та В взаємно перетворювані, то вони називаються еквівалентними.
Твердження 1. (нижні оцінки методом перетворення). Якщо відомо, що задача А вимагає Т(N) часу і (задача A перетворювана в задачу В), то В можна розв'язати за час не менший за T(N) - O(r(N)).
Твердження 2. (верхні оцінки методом перетворення). Якщо задачу В можна розв'язати за час Т(N) і (задача A перетворювана в задачу В), то А можна розв'язати за час, який не перевищує T(N)+O(r(N)).