Зачем использовать языки в теории сложности

Я только начинаю изучать теорию вычислений, которая изучает, что можно вычислить, как быстро, сколько памяти и с какой вычислительной моделью.

У меня довольно простой вопрос, но я очень надеюсь, что некоторые из вас, ребята, помогут мне понять концепцию, лежащую в основе этого:

Почему все сосредоточено вокруг понятия и определения ЯЗЫКОВ (т.е. обычных языков и языков без контекста)? И как они связаны и описывают сложность алгоритма и возможные вычислительные модели для их решения?

Я читаю подобные вопросы:

• /cstheory/14811/what-is-the-enlightenment-im-supposed-to-attain-after-studying-finite-automata
• /cstheory/8539/how-practical-is-automata-theory

но до сих пор нет ответа на мои сомнения, поскольку они дают практическое обоснование того, почему они важны (что я понимаю), но не помогают мне понять, почему теория сложности основана на них.

Это потому, что языки - лучший (единственный?) Способ формализации понятия «проблема».

Алгоритм (машина Тьюринга) обладает производительностью, которую мы выражаем через сложность big-O. Задача (язык) относится к классу сложности. Они обычно определяются существованием: если существует машина, принимающая язык который работает с заданной производительностью (пространство или время), то язык принадлежит соответствующему классу сложности.$L$

Есть несколько причин для этого. Во-первых, языки независимы от платформы. Вы не беспокоитесь о том, является ли целое число 32- или 64-разрядным, или же операции с плавающей запятой выполняются параллельно с другими операциями. Эти вещи повышают производительность на микроуровне, но анализ сложности интересует макроуровень. При масштабировании от 100 до до до входов, как изменяется производительность алгоритма? Означает ли это использование 1 миллиона ленточных ячеек до 1 миллиарда или от 1 миллиона до большего количества ячеек, чем атомов во вселенной?10 9 10 $10^6$$10^9$$10^{12}$

Во-вторых, языки - это просто хорошая абстракция для данных. Вам нужно что-то, что вы можете сделать доказательства, что вы можете моделировать формально. Кодирование ввода и вывода в виде строки означает, что теперь вы имеете дело не с битами в памяти, а с математическими объектами с определенными свойствами. Вы можете рассуждать о них и доказывать доказательства в формальном и очень простом смысле.

Теория сложности, как правило, ориентирована на решение проблем, потому что они оказываются сложными. Когда версия решения коммивояжера является NP-полной (т. Е. Есть ли тур, длина которого меньше длины ), то, очевидно, найти кратчайший путь труднее. Не так много внимания уделяется проблемам функций / оптимизации, потому что есть еще много открытых вопросов и нерешенных проблем, связанных с более простыми проблемами решения.$k$

Я думаю, вот моя задача для вас: найти способ математически описать проблемы, которые не являются языками. Я не знаю, являются ли языки особенными, но я думаю, что это самый простой инструмент, который у нас есть, самый простой, с которым приходится иметь дело.

На ваш вопрос есть два основных ответа:

1. В теории сложности есть нечто большее, чем в языках, например, классы функций, арифметическая сложность, а также подрайоны алгоритмов аппроксимации и неприемлемости.

2. Исторические причины: одна из основных статей в теории вычислимости была посвящена проблеме Энтшайдунгса Гильберта (форма проблемы остановки).

К сожалению, я не знаю много о последнем, но позвольте мне остановиться на первом.

Сложность за пределами языков

Каждый класс сложности вычислений поставляется со связанным классом функций . Например, класс P всех задач, разрешимых за полиномиальное время, связан с FP, классом всех функций, вычислимых за полиномиальное время. FP имеет важное значение , так как он используется для определения NP-твердость: язык является NP-трудной , если для каждого языка в НП есть функция в FP , такие , что тогда и только тогда . Другой класс сложности функций, #P , связан с так называемой полиномиальной иерархией через теорему Тоды .M f M x ∈ M f M ( x ) ∈ $L$$M$$f_M$$x \in M$$f_M(x) \in L$

Арифметическая сложность схемы (или теория алгебраической сложности ) имеет дело со сложностью вычисления различных многочленов. Важными классами сложности здесь являются VP и VNP, а геометрическая теория сложности является важным проектом, пытающимся разделить VP и VNP (а затем и P и NP) с использованием алгебраической геометрии и теории представлений.

Другим важным примером алгебраической сложности является быстрое умножение матриц. Здесь основной вопрос заключается в том, как быстро мы можем умножить две матрицы ? Подобные вопросы спрашивают, как быстро мы можем умножать целые числа, как быстро мы можем проверять целые числа на простоту (это проблема решения!) И как быстро мы можем вычислять целые числа.

Выпуклая оптимизация имеет дело с задачами оптимизации, которые могут быть решены (или почти решены) эффективно. Примерами являются линейное программирование и полуопределенное программирование, оба из которых имеют эффективные алгоритмы. Здесь нас интересует как оптимальное, так и само оптимальное решение. Поскольку часто существует более одного оптимального решения, вычисление оптимального решения не всегда представляется проблемой решения.

Аппроксимируемость - это область, которая изучает, насколько хорошее приближение можно получить для задачи оптимизации за полиномиальное время. Рассмотрим, к примеру, классическую проблему Set Cover: учитывая набор множеств, сколько из них нам нужно, чтобы охватить всю вселенную? Найти оптимальное число сложно с NP, но, возможно, можно вычислить приближение? Алгоритмы аппроксимации - это подрайон, изучающий алгоритмы для вычисления аппроксимаций, в то время как не приближаемость изучает пределы алгоритмов аппроксимации. В частном случае Set Cover у нас есть алгоритм, дающий аппроксимацию (жадный алгоритм), и NP-сложнее сделать что-то лучше.$\ln n$

Давайте посмотрим на этот вопрос с точки зрения теории категорий. Задачи решения (или языки) будут тогда соответствовать объектам категории, а допустимые сокращения между двумя проблемами будут соответствовать морфизму (стрелкам) категории.

Преимущество разговоров о языках заключается в том, что эквивалентность языков четко определена (а именно равенством экстенсиональности). Две несвязанные проблемы могут привести к одному и тому же языку, и тогда мы можем рассматривать их как эквивалентные. Если бы мы вместо этого хотели поговорить об изоморфных проблемах, нам пришлось бы определить допустимые морфизмы между двумя проблемами. Но допустимые морфизмы зависят от рассматриваемого фактического класса сложности, что делает этот подход менее подходящим для сравнения различных классов сложности.

Понятие изоморфных проблем обычно будет более грубым, чем понятие эквивалентных языков, то есть две проблемы могут быть изоморфными, даже если связанные с ними языки не эквивалентны. Хуже всего то, что для разрешенных морфизмов часто существуют разные разумные понятия, которые согласуются только с разрешенными изоморфизмами. Сосредоточение внимания на языках позволяет откладывать такие проблемы до тех пор, пока мы не захотим говорить о некоторых других разумных понятиях сокращения (например, сокращение Карпа против уменьшения Кука).