Теория комплексности

Теория комплексности относится к разделу прикладной математики и является частью теории алгоритмов. Теория комплексности может также называться теорией вычислительной сложности. Теория появилась во второй половине 20-го века, когда учёные на всё более мощных компьютерах пытались и отчасти находили решения задачам из раздела исследование операций.

Основная суть теории

Основная суть теории заключается в категоризации разного вида задач в определённые классы по степеням сложности их решений. Сложность решения задачи при этом измеряется соотношением роста количества переменных в задаче к росту количества компьютерного времени необходимого для решения этих задач. Простым классом является класс задач решаемый в "полиномиальном " приросте компьютерного времени. Сложным классом является класс задач решаемый в "экспоненциальном " приросте компьютерного времени. И предметом активного исследования является класс, который называют "не предопределённым полиномиальным " ( _en. Non Determenistic Polynomial). Задачи этого класса называют также ΝΠ-сложными (NP-сложными) или ΝΠ-трудными (NP-трудными). Теория комплексности занимается так же исследованием свойств этих классов и исследованием возможности трансформации задач одного типа класса (сложного) в другой (более простой) в полиномиальном времени.