Категория NP-полных задач?

28

Имеет ли смысл рассматривать категорию всех NP-полных задач с морфизмами как сокращение временного промежутка между различными экземплярами? Кто-нибудь когда-либо публиковал статью об этом, и если так, где я могу найти это?

Пол Аллен Граббс
источник
1
Я не уверен, почему вам нужна категория только NP-полных задач, но категория всех проблем с решениями с некоторым фиксированным понятием сокращений (таких как сокращения многочлена за полиномиальное время) как морфизмы звучит разумно для рассмотрения. Я вообще не знаю теорию категорий и не могу догадаться, интересна она или нет.
Цуёси Ито
1
Не уверен, что это поможет, но я попробую: об изоморфизмах и плотности NP и других комплектациях . Смотрите также версию журнала . Смотрите также статью Махани .
MS Dousti
2
Просто хотел уточнить комментарий Садека. Изоморфизм между полными проблемами был изучен, и была проделана большая работа по доказательству / опровержению гипотезы Бермана-Хартманиса (которая утверждает, что все полные проблемы являются «изоморфными» при полиномиальном уменьшении много-один раз). Вот обзор Маниндры Агравал о гипотезе об изоморфизме ( cse.iitk.ac.in/users/manindra/survey/Isomorphism-Conjecture.pdf ). Н ПNPNP
Рампрасад
1
@Tsuyoshi: даже категория проблем NPC с сокращением Карпа может быть интересной - если бы мы действительно понимали даже эту категорию, у нас было бы намного лучшее понимание сложности в целом (поскольку это, вероятно, повлекло бы за собой гораздо лучшее понимание Карпа сокращения, следовательно, полиномиального времени). OTOH, я не уверен, что просмотр его как категории обеспечит путь к пониманию. Я думал об этой проблеме в прошлом и искал ссылки, которые рассматривают сложность таким образом, и не нашел ни одной. Я надеюсь, что кто-то делает!
Джошуа Грохов
3
Я второй Джошуа. Важно то, что невозможно определить категорию, важно найти в ней интересную категориальную структуру. В случае вычислимости есть интересные структуры, но по сложности я не знаю. Андрей должен знать лучше и, надеюсь, проверит этот вопрос.
Каве

Ответы:

21

Область, которую вы хотите посмотреть, называется «теория неявной сложности». Случайный и неполный список имен для Google - Мартин Хофманн, Патрик Бейло, Уго Дал Лаго, Симона Рончи Делла Рокка и Казушиге Теруи.

Основной метод состоит в том, чтобы связать классы сложности с подсистемами линейной логики (так называемые «легкие линейные логики»), с идеей, что исключение разреза для логической системы должно быть полным для данного класса сложности (такого как LOGSPACE, PTIME и т. Д.). Затем через Curry-Howard вы получаете язык программирования, на котором точно выражены программы в данном классе. Как можно ожидать из упоминания о линейной логике, все эти системы порождают моноидальные замкнутые категории различных ароматов, что дает вам чисто алгебраическую и машинно-независимую характеристику различных классов сложности.

Одна из вещей, которая делает эту область интересной, заключается в том, что ни традиционная сложность, ни логические / PL-методы не совсем уместны.

Поскольку участвующие категории обычно имеют замкнутую структуру, комбинаторные методы, предпочитаемые теоретиками сложности, часто ломаются (поскольку программы более высокого порядка имеют тенденцию сопротивляться комбинаторным характеристикам). Типичным примером этого является неспособность синтаксических методов обрабатывать контекстную эквивалентность. Точно так же методы семантики также имеют проблемы, так как они часто слишком экстенсиональны (поскольку традиционно семантики хотели скрыть внутреннюю структуру функций). Простейший пример, который я знаю здесь, это закрытие LOGSPACE под композицией: это AFAIK возможно только из-за согласования и выборочного пересчета, и вы не можете рассматривать проблемы как чисто чёрные ящики.

Вы, вероятно, также захотите ознакомиться с семантикой игры и геометрией взаимодействия Джирарда (и их предшественником, конкретными структурами данных Кана-Плоткина-Берри), если вы серьезно зайдете в эту область - с идеями прохождения токенами представлений высшего уровня. Расчеты заказов, использованные в этой работе, дают много интуиции для ICC.

Поскольку я указал на центральную роль моноидальных категорий в этой работе, вы можете разумно задуматься о связи с GCT Малмулей. К сожалению, я не могу вам здесь помочь, так как просто не знаю достаточно. Пол-Андре Меллиес может быть хорошим человеком, чтобы спросить, хотя.

Нил Кришнасвами
источник
16

Можно классифицировать много вещей, но это не обязательно означает, что они интересные категории. Таким образом, ответ «имеет ли смысл» зависит от того, как вы имеете в виду.

Что касается предсказания того, будет ли это интересно, примите какое-то подходящее определение сокращений, чтобы оно сформировало категорию NPC. К категории теоретически интересных вопросов относятся такие вещи, как вопрос о том, имеет ли NPC различные ограничения или ограничения (например, продукты, побочные продукты, откаты, выпады, ...). Поэтому, прежде чем приступить к работе по формализации вещей, было бы хорошо сесть и подумать о том, что означают эти ограничения, и будет ли интересно узнать это значение. Если мы предположим, что у NPC есть откаты, то означает ли возможность откатить два снижения что-нибудь особенное? Подобные вопросы кажутся интересными, если мы хотим выяснить, что такое «атомарные» NP-полные проблемы или как можно объединить несколько NP-полных задач (или их сокращение);

Следующие вопросы могут быть такими: есть ли у NPC какие-нибудь интересные подкатегории? NPC - это подкатегория каких-либо интересных больших категорий? Мы уже знаем много о том, как NP-полные проблемы связаны с другими классами проблем, поэтому предполагаемый ответ на эти вопросы «конечно». Но чтобы уточнить это, что дает возможность рассмотреть эти отношения с теоретической точки зрения категории, чего нет у других? Одна вещь, которую CT может предложить, это вопрос о том, существуют ли какие-либо нетривиальные примыкания между NPC и другой категорией. Конечно, пристрастия в основном интересны, когда категории, стоящие за ними, сами по себе интересны, поэтому, если у NPC нет особой структуры, знание о пристрастиях NPC действительно не принесет многого.

Что касается конкретных ссылок, я не знаю ничего о нём, но ссылки в комментариях Sadeq, Ramprasad, Kaveh должны предоставить где-то начать.

Рен Романо
источник