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

Время, память и нотация Big O

В своей основе теория вычислительной сложности занимается количеством времени и памяти, которые требуются алгоритму для решения задачи. Временная сложность означает количество шагов, которые выполняет алгоритм, а пространственная сложность — объём используемой памяти. Эти две меры являются фундаментальными для оценки эффективности алгоритма, и обе обычно выражаются с помощью нотации Big O, задающей верхнюю границу количества шагов или объёма памяти. Поскольку Big O описывает, как растёт потребление ресурсов относительно размера входных данных, а не скорость на конкретном оборудовании, она позволяет сравнивать алгоритмы независимо от машин, на которых они выполняются.

P и NP: фундаментальные классы

Два наиболее значимых класса в теории вычислительной сложности — это P (от англ. Polynomial Time, полиномиальное время) и NP (от англ. Nondeterministic Polynomial Time, недетерминированное полиномиальное время). Класс P состоит из задач разрешения, которые могут быть решены за полиномиальное время детерминированной машиной Тьюринга, то есть время выполнения растёт не быстрее полиномиально с увеличением размера входных данных. NP, напротив, включает задачи разрешения, для которых предложенное решение может быть проверено за полиномиальное время детерминированной машиной Тьюринга, хотя само решение может не находиться быстро.

Вопрос о том, равно ли P NP, остаётся одним из самых глубоких открытых вопросов информатики. Если P=NP, то каждая задача, для которой известен эффективный метод проверки, имеет и эффективный алгоритм поиска решения. Если P≠NP, то существуют задачи, для которых эффективного алгоритма нет, даже если решение можно эффективно проверить. Насколько велика ставка в этом вопросе, отражает его включение в число семи «Задач тысячелетия», учреждённых Институтом Клэя, каждая из которых сопровождается премией в 1 миллион долларов за решение. Ответ на этот вопрос имеет существенные последствия для криптографии, задач оптимизации и многих областей науки и техники, учитывая, что значительная часть современной криптографии опирается на предположение о том, что некоторые задачи невозможно решить за практически приемлемое время.

Сведения и NP-полнота

Ключевым понятием при доказательстве сложности задач является сведение, при котором одна задача преобразуется в другую. Если задача A может быть сведена к задаче B, а B заведомо сложна, то A не менее сложна, чем B. NP-полные задачи — это задачи из NP, которые не менее сложны, чем самые трудные задачи в NP. Если какая-либо NP-полная задача окажется решаемой за полиномиальное время, то P=NP. Известные примеры NP-полных задач включают задачу комивояжёра, задачу о выполнимости булевых формул (SAT) и задачу о рюкзаке. Такие задачи далеки от чисто академических: они регулярно возникают в маршрутизации, планировании и распределении ресурсов, и там, где эффективный точный алгоритм неизвестен, на практике обычно применяются приближённые алгоритмы и эвристики, которые жертвуют гарантированной оптимальностью ради приемлемого времени выполнения.

Теория вычислительной сложности предоставляет богатую основу для понимания тонкостей эффективности алгоритмов и пределов вычислений. Через призму P, NP и сведений исследователи получают представление о фундаментальных сложностях эффективного решения комплексных задач. Поскольку вычисления играют всё большую роль в повседневной жизни, изучение теории вычислительной сложности остаётся жизненно важным, указывая путь к более эффективным решениям и проливая свет на границы того, что вообще может быть вычислено. Пока вопрос «P против NP» не решён, граница между задачами, для которых известны эффективные решения, и задачами, для которых их не найдено, будет продолжать определять как приоритеты исследований, так и инженерную практику.

Источник: OPEC