Алгори́тм — совокупность точно заданных правил решения некоторого класса задач или набор инструкций, описывающих порядок действий исполнителя для решения определённой задачи. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.
Быстрое преобразование Фурье — алгоритм ускоренного вычисления дискретного преобразования Фурье, позволяющий получить результат за время, меньшее чем 
. Иногда под быстрым преобразованием Фурье понимается один из алгоритмов, называемый алгоритмом прореживания по частоте — времени, имеющий сложность 
.
NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «типовых» задач в классе NP: если для какой-то из них будет найден «полиномиально быстрый» алгоритм решения, то и любую другую задачу из класса NP можно будет решить так же «быстро».
В теории алгоритмов классом P называют множество задач, для которых существуют «быстрые» алгоритмы решения. Класс P включён в более широкие классы сложности алгоритмов.
В теории алгоритмов классом NP называют множество задач разрешимости, решение которых возможно проверить на машине Тьюринга за время, не превосходящее значения некоторого многочлена от размера входных данных, при наличии некоторых дополнительных сведений.
Класс сложности PH — объединение всех классов сложности из полиномиальной иерархии:
Откры́тые (нерешённые) математи́ческие пробле́мы — задачи, которые рассматривались математиками, но до сих пор не решены. Часто имеют форму гипотез, которые предположительно верны, но нуждаются в доказательстве.
В теории алгоритмов классом сложности BPP называется класс предикатов, быстро вычислимых и дающих ответ с высокой вероятностью. Задачи, решаемые вероятностными методами и лежащие в BPP, возникают на практике очень часто.
Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется объёмом памяти или места на носителе данных. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа?». Здесь под размером входа понимается длина описания данных задачи в битах, а под размером выхода — длина описания решения задачи.
Класс сложности PSPACE — набор всех проблем разрешимости в теории сложности вычислений, которые могут быть разрешены машиной Тьюринга с полиномиальным ограничением пространства.
В теории сложности полиномиальная иерархия — это иерархия классов сложности, которая обобщает классы P, NP, co-NP до вычислений с оракулом.
В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе. Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, то есть при стремлении размера входа к бесконечности. Например, если существует число 
, такое, что время работы алгоритма для всех входов длины 
не превосходит 
, то временную сложность данного алгоритма можно асимптотически оценить как 
.
Тео́рия алгори́тмов — раздел математики, изучающий общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п. Вместе с математической логикой теория алгоритмов образует теоретическую основу вычислительных наук, теории передачи информации, информатики, телекоммуникационных систем и других областей науки и техники.
Пермане́нт в математике — числовая функция, определённая на множестве всех матриц; для квадратных матриц похожа на детерминант, и отличается от него лишь в том, что в разложении на перестановки берутся не чередующиеся знаки, а все плюсы. В отличие от детерминанта, определение перманента расширено и на неквадратные матрицы.
Теория сложности вычислений — подраздел теоретической информатики, занимающейся исследованием сложности алгоритмов для решения задач на основе формально определённых моделей вычислительных устройств. Сложность алгоритмов измеряется необходимыми ресурсами, в основном это продолжительность вычислений или необходимый объём памяти. В отдельных случаях исследуются другие степени сложности, такие как размер микросхем, или количество процессоров, необходимая для работы параллельных алгоритмов.
Квадрати́чная зада́ча о назначе́ниях — одна из фундаментальных задач комбинаторной оптимизации в области оптимизации или исследования операций, принадлежащая категории задач размещения объектов.
Мощность неориентированного графа — характеристика графа, равная минимальному отношению количества рёбер, удалённых из графа, к числу компонент, полученных в результате такого удаления. Этот метод позволяет определить зоны высокой концентрации рёбер. Мощность графа сходна с понятием жёсткости графа, которая, однако, определяется через процедуру удаления вершин, а не рёбер.
Квантовая теория сложности — часть теории сложности вычислений в теоретической информатике. Изучает классы сложности, определённые с использованием квантовых компьютеров и квантовой информации, а также проблемы, связанные с этими классами сложности, и связи между классами квантовой сложности и классическими (неквантовыми) классами сложности.
В теории сложности вычислений классом NC называют множество задач разрешимости, разрешимых за полилогарифмическое время на параллельном компьютере с полиномиальным числом процессоров. Другими словами, задача принадлежит классу NC, если существуют константы n и c такие, что она может быть решена за время 
при использовании 
параллельных процессоров. Стивен Кук назвал его «Классом Ника» в честь Ника Пиппенжера, который провел обширные исследования схем с полилогарифмической глубиной и полиномиальным размером.
