Каковы некоторые нетривиальные задачи, в которых мы знаем, что текущий алгоритм, который у нас есть, является асимптотически оптимальным? (Для машин Тьюринга) И как это...
За последние два десятилетия была проделана фантастическая работа над перманентом. Некоторое время я размышлял о возможности алгоритма Smooth P для перманента неотрицательных матриц. Конечно, есть известный алгоритм JSV, но это fpras. Думая о другой работе в рамках Сглаженной Сложности, сильным...
Учитывая два CNF, если они имеют одинаковое количество назначений, чтобы сделать их правдой, ответьте «Да», в противном случае ответьте «Нет». Легко увидеть, что это в P#PP#PP^{\#P} , поскольку, если мы знаем точное число решений этих двух CNF, мы просто собираем их и отвечаем «Да» или «Нет». В чем...
1) Возможно ли экономное сокращение от # P-полной задачи #A до проблемы подсчета #B, когда (версия решения) A является NP-полной, а B находится в P? Например, может ли быть экономное сокращение от #SAT до #B, когда B находится в P? 2) Если B находится в P, каковы различные возможности для сложности...
Я провел некоторый поиск по этому вопросу, но так или иначе не смог найти ответ. Гек ответил на это полностью. Благодарность
Я знаю, что (логарифмически много обращений к оракулу NP) эквивалентно P N P | | (полиномиальное количество параллельных запросов к NP oracle). Мне было интересно, "функциональные" версии этих классов также эквивалентны, то естьPNP[logN]PNP[logn]\mathsf{P}^{\mathsf{NP}[\log n]}пН П |...
Есть ли интересные проблемы, которые есть в но неизвестно, что они есть в ? В статье «Таксономия проблем с быстрыми параллельными алгоритмами» Кук упоминает, что MIS, как было известно, находится только в но с тех пор он был переведен в , Мне интересно, есть ли какие-либо другие проблемы с...
Долгое время я думал, что задача была NP-полной, если она (1) NP-сложная и (2) в NP. Однако в известной статье «Метод эллипсоидов и его последствия в комбинаторной оптимизации» авторы утверждают, что проблема дробного хроматического числа принадлежит NP и является NP-сложной, но пока неизвестно,...
Этот вопрос был задан Яном Паксом в списке рассылки « Основы математики» . Конечно, но из ответов на этот вопрос я подозреваю , что неизвестно, будет ли (в противном случае будет одним возможный ответ на этот вопрос). Если не известно, существует ли разделение...
Я читаю приложение о АССЕ нижних границах для NEXP в Arora и Барак вычислительной сложности книги. http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf Одна из ключевых лемм - это преобразование из цепей в полилинейные полиномы над целыми числами с полилогарифмической степенью и...
Класс сложности PPAD обычно определяется указанием того, что End-Of-The-Line является PPAD-завершенным. End-Of-The-Line - это проблема поиска. Входные данные состоят из ориентированного графа, в котором у каждого узла максимальная и минимальная степени равны 1. Граф задается вычисляемой функцией...
Многие классы сложности, определенные с помощью машин Тьюринга, имеют определения в терминах однородных цепей. Например, P также может быть определен с использованием схем с однородным полиномиальным размером, и аналогично BPP, NP, BQP и т. Д. Могут быть определены с помощью однородных схем. Так...
Недавний вопрос (см Последствия NP = PSPACE ) просил для "противных" последствий . Перечисляют ответы немало последствий обрушения, в том числе N P = C O N P и другие, обеспечивая множество причин полагать N P ≠ P S P A C E .NP=PSPACENP=PSPACENP=PSPACENP=coNPNP=coNPNP=coNPNP≠PSPACENP≠PSPACENP\neq...
Каждый раз, когда я преподаю NP-Полноту, студенты спрашивают: «Есть ли проблемы, о которых известно, что они не относятся к NP?» Как бы вы ответили? Я обычно даю им неразрешимую проблему в качестве примера, но это часто не очень хорошо получается: (а) если я дам им проблему остановки, они думают,...
Теорема Раза о параллельном предсказании является важным результатом в PCP, аппроксимации и т. Д. Теорема оформилась следующим образом. Игра , где S , T , A , B - конечные множества, π - распределение по S × T и предикат V : S × T × A × B → { 0 , 1 } . Определить значение игры v ( G ) = max...
P / poly - это класс задач решения, решаемых семейством булевых схем полиномиального размера. В качестве альтернативы его можно определить как машину Тьюринга за полиномиальное время, которая получает строку подсказки, которая имеет полиномиальный размер по n и основана исключительно на размере n....
Могут ли все последующие одновременно выполняться? LsLsL_s содержится в для всех натуральных чисел . sLs+1Ls+1L_{s+1}sss L=⋃sLsL=⋃sLsL = \bigcup_s L_s - это язык всех конечных слов над .{0,1}{0,1}\{0,1\} Существует некоторый класс сложности и понятие соответствующего сокращения для такой , что для...
Рассмотрим следующую игру на ориентированном взвешенном графе гGG с чипом в некотором узле. Все узлы гGG отмечены буквой A или B. Есть два игрока Алиса и Боб. Цель Алисы (Боба) - сдвинуть фишку к узлу, обозначенному буквой A (B). Первоначально Алиса и Боб имеют мAmAm_A и мВmBm_B долларов...
Какие еще языки проблем, отличные от изоморфизма графов, есть в ? Можете ли вы дать некоторые ссылки?Nп∩ c o A MNP∩coAMNP\cap coAM Обновление: Я забыл упомянуть , что я заинтересован в языках , не известно, в .c o...
Автор: http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf. Если является PSPACE-полный язык, Р = N P A .AAAпA= NпAPA=NPAP^{A}=NP^{A} Если является детерминированным оракулом полиномиального времени, P B ≠ N P B (при условии, что P ≠ N P ).ВBBпВ≠ NпВPB≠NPBP^{B}\ne NP^{B}п≠ NпP≠NPP\ne NP -...