Лог-пространство-равномерный NC содержится в детерминированном пространстве полилога (иногда пишется PolyL). Является ли лог-пространственно-равномерный RNC также в этом классе? Стандартная рандомизированная версия PolyL должна быть в PolyL, но я не вижу, чтобы (равномерный) RNC был в...
Parity-L - это набор языков, распознаваемых недетерминированной машиной Тьюринга, которые могут различать только четное число или нечетное число путей «принятия» (а не нулевое или ненулевое число путей принятия), и который далее ограничено работой в логарифмическом пространстве. Решение линейной...
Читая статью «Пора ли объявить победу в подсчете сложностей?» в блоге «Потерянное письмо Годеля и P = NP» они упомянули дихотомию для CSP. После некоторой ссылки, поиска в Google и википедирования, я наткнулся на теорему Ладнера : Теорема Ладнера: если , то в N P ∖ P существуют проблемы , которые...
Шива Кинтали только что объявил (круто!) Результат, что изоморфизм графов для ограниченных графов ширины является ⊕ L- трудным≥4≥4\geq 4⊕L⊕L\oplus L . Неофициально мой вопрос: "Насколько это сложно?" Мы знаем, что неравномерно , см. Ответы на этот вопрос . Мы также знаем, что маловероятно, что ,...
Каковы будут последствия #P = FP? Меня интересуют как практические, так и теоретические последствия. С практической точки зрения меня особенно интересуют последствия для искусственного интеллекта. Указатели на бумаги или книги более чем приветствуются. Пожалуйста, не говорите, что #P = FP...
Исследование сжатого представления графов было начато Гальперином и Вигдерсоном в статье 1983 года, где они доказывают, что для многих простых задач, таких как нахождение треугольника на графе, соответствующая краткая версия в NPNP\mathsf{NP} -полна. Papadimitriou и Yanakkakis дальнейшее это...
Существуют ли какие-либо естественные проблемы в , которых нет (как известно / считается, что они есть) в ?U P ∩ c o U PNп∩ c o NпNP∩coNPNP \cap coNPUп∩ c o UпUP∩coUPUP \cap coUP Очевидно, что большая часть, о которой все знают в - это вариант факторинга для решения (не имеет ли коэффициент размера...
Недавно Райан Уилламс доказал, что конструктивность в естественном доказательстве неизбежно приводит к разделению классов сложности: и . N E X PNЕИксп\mathsf{NEXP}Т С0TС0\mathsf{TC}^{0} Конструктивность в естественном доказательстве - это условие, которому удовлетворяют все комбинаторные...
Эй, ребята, я понимаю, что уловка заполнения позволяет нам переводить классы сложности вверх - например, . Заполнение работает, «раздувая» ввод, выполняя преобразование (скажем, от к ), что приводит к «волшебному» алгоритму, который вы можете запустить на дополненном вводе. Хотя это имеет...
Это связано с вопросом: известен ли размер свидетельства для каждого языка NP, уже известного? Некоторые естественные задачи (-complete) имеют свидетелей линейной длины: удовлетворительное назначение для S A T , последовательность вершин для H A M P A T H и т. Д.Н ПNP\mathsf{NP}SА ТSATSATЧАСА МпА...
Существует богатая литература и, по крайней мере, одна очень хорошая книга, в которой излагаются известные значения твердости аппроксимации для NP-трудных задач в контексте мультипликативной ошибки (например, 2-аппроксимация для покрытия вершин оптимальна при условии UGC). Это также включает хорошо...
Каковы убедительные причины верить L ≠ PL≠PL\neq P ? L - класс алгоритмов лог-пространства с указателями на вход. Предположим, что L = P на данный момент. Как будет выглядеть алгоритм лог-пространства для P-полной задачи в общих...
Теория сложности, с помощью таких понятий, как NP-полнота, различает вычислительные задачи, которые имеют относительно эффективные решения, и те, которые трудноразрешимы. «Мелкозернистая» сложность призвана уточнить это качественное различие в количественном руководстве относительно точного...
Рассмотрим задачи оптимизации следующего вида. Пусть f(x)f(x)f(x) - вычислимая функция полиномиального времени, которая отображает строку xxx в рациональное число. Задача оптимизации заключается в следующем: что максимальное значение f(x)f(x)f(x) над nnn -битовый строки xxx ?...
Читая ответ Питера Шора и предыдущий вопрос Адама Крума, я понял, что у меня есть некоторые неправильные представления о том, что значит быть -hard.PP\mathsf{P} Проблема -hard, если любая проблема в сводится к ней с помощью (или если вы предпочитаете ) сокращений. Проблема находится вне если не...
В этой теме попытка Нобетта Блюма в доказательстве лаконично опровергается, когда отмечается, что функция Тардоса является контрпримером к теореме 6P≠NPP≠NPP \neq NP Теорема 6 : Пусть - любая монотонная булева функция. Предположим, что существует CNF-DNF-аппроксиматор который можно использовать для...
Интересно, есть ли основания полагать, что или верить, что N L ≠ L ?NL = LNL=LNL=LNL ≠ LNL≠LNL\neq L Известно, что . Литература по derandomization из R L является довольно убедительным , что R L = L . Кто-нибудь знает о каких-то статьях или идеях, убеждая, что N L ≠ L ?NL ⊂ L2NL⊂L2NL \subset L^2R...
Это своего рода открытый вопрос, за который я заранее прошу прощения. Существуют ли примеры утверждений, которые (казалось бы) не имеют ничего общего со сложностью или машинами Тьюринга, но ответ на них подразумевал бы ?P ≠ N PP≠NP\mathbf{P}\neq...
Равен ли BQP BPP с доступом к оракулу скрытой абелевой
Вдохновленный вопросом, что факторинг известен как P-hard , мне интересно, каково текущее подобное состояние знаний о твердости изоморфизма графов. Я уверен, что в настоящее время неизвестно, находится ли G в P, но: какой самый известный в настоящее время класс, чем GI сложнее? (не было ответа на...