Мой вопрос заключается в том, почему нижние оценки для логических схем глубины 3 с логическими элементами "и" и "xor" для определителя не подразумевают такие же нижние оценки для арифметических схем над ?ZZ\mathbb{Z} Что не так со следующим аргументом: Пусть - определитель, вычисляющий...
Я ищу ссылки на сложность проблемы балансировки булевых формул . В частности, Было ли известно, что булевы формулы могут быть сбалансированы в ?AC0AC0\mathsf{AC^0} Есть ли простое доказательство балансировки булевой формулы в ?AC0AC0\mathsf{AC^0} Под «простым» я подразумеваю доказательство, более...
Пусть класс BPNC (комбинация и ) будет параллельным алгоритмом глубины логарифма с ограниченной вероятностью ошибки и доступом к случайному источнику (я не уверен, что у него другое имя). Определите класс DBPNC аналогичным образом, за исключением того, что все процессы имеют произвольный доступ к...
В разговоре Разборова опубликовано любопытное небольшое заявление. Если ФАКТОРИНГ труден, то маленькая теорема Ферма не доказуема в .S12S21S_{2}^{1} Что такое и почему текущих доказательств нет в ? S 1...
BPPBPP\mathsf{BPP} иZPPZPP\mathsf{ZPP} - два основных класса вероятностной сложности. BPPBPP\mathsf{BPP} - это класс языков, определяемых вероятностными алгоритмами Тьюринга за полиномиальное время, где вероятность возврата неправильного ответа ограничена, т. Е. Вероятность ошибки не...
В сложности связи гипотеза лог-ранга утверждает, что с с ( М) = ( журналr k ( М) )O ( 1 )cc(M)=(logrk(M))O(1)cc(M) = (\log rk(M))^{O(1)} Где - сложность связи а - ранг (в виде матрицы) над реалами.M ( x , y ) r k ( M ) Mс с ( М)cc(M)cc(M)M( х , у)M(x,y)M(x,y)r k ( М)rk(M)rk(M)MMM Однако, когда вы...
Класс сложности определяется следующим образом (из Википедии ):Sп2S2P\textrm{S}_2^\textrm{P} Язык находится в S P 2, если существует предикат P полиномиального времени, такой чтоLLLSп2S2PS_2^PпPP Если , то существует такой y , что для всех z , P ( x , y , z ) = 1x ∈ Lx∈Lx \in LYyyZzzп( х , у, z) =...
Является ли граф изоморфизмом (проблемой решения) в ? Здесь U P - класс решений проблем, принимаемых однозначной машиной Тьюринга (см. Зоопарк сложности ).UP∩coUPUP∩coUP\mathsf{UP}\cap...
Я пытался понять эти классы, но всегда запутался ... вопросы: Какова связь между и , в частности это открытый вопрос?FNPFNPFNP#P#P\#P Какое отношение имеют и ? этот вопрос открыт?⊕P⊕P\oplus PNPNPNP Как насчет отношений между и ? этот вопрос...
Покрывающее дерево графа называется деревом полноты, если множество его листьев индуцирует полный подграф в графе хоста. Учитывая граф и целое число , какова сложность определения, содержит ли дерево полноты с максимум листами?ггGККkггGККk Причина для того, чтобы задать этот вопрос, состоит в том,...
Для заданного набора из точек в d- мерном евклидовом пространстве задача состоит в том, чтобы определить, содержит ли выпуклая оболочка единичный шарик с центром в начале координат.NNnddd Эта проблема в NP? Это в co-NP, поскольку можно указать точку в шаре вне выпуклой оболочки в качестве свидетеля...
У меня есть следующая проблема: Вход: два набора интервалов и T (все конечные точки являются целыми числами). Вопрос: существует ли монотонная биекция f : S → T ?SSSTTTе: S→ Tf:S→Tf:S \to T Биекция монотонна WRT порядка включения множества на и T . ∀ X ⊆ Y ∈ S , f ( X ) ⊆ f ( Y )SSSTTT∀ X⊆ Y∈ S,...
Если мы можем доказать, что , означает ли это, что ?L=PL=P\mathsf{L}=\mathsf{P}NL=NPNL=NP\mathsf{NL}=\mathsf{NP} Я думал, что это так, но я не могу доказать это (также для
Учитывая направленный граф, мы хотим решить, содержит ли он направленный цикл четной длины. В этой статье 1997 года, написанной YUSTER и ZWICK, утверждается, что проблема не в том, что она находится в а также в том, что она не является N P -полной.ппPNпNпNP Есть ли какой-либо недавний результат,...
Я наткнулся на открытую проблему, поставленную Дэвидом Эппштейном, и меня интересует ее сложность. Он предположил, что он NP-завершен. Ввод: по n матриц 0 и 1, последовательность n 2 0 и 1nnnnnnn2n2n^2 Вопрос: существует ли путь через соседние элементы матрицы, охватывающий каждую запись матрицы...
Давайте назовем язык NP редко сертифицированным тогда и только тогда, когда:L ∈L∈L \in Существует такой многочлен , что для каждого входа x ∈ Σ ∗ размера n , если x ∈ L, то множество U x сертификатов u, которые проверяют, что x ∈ L имеет полиномиальный размер, т. Е. | U x | ≤ p ( n ) .p : N →...
Каково стандартное определение Planar 3-SAT? Я видел много разных определений. Какая оригинальная статья определила ее и доказала, что она является
В разделе «Расширенные темы по типам и языкам программирования» в главе, посвященной системам субструктурных типов, упоминается, что «тщательно разработанное» аффинное лямбда-исчисление с рекурсивным комбинатором для списков может вводить только те термины, которые имеют полиномиальное время...
Существуют ли проблемы, которые разрешимы за полиномиальное время, только если P! = NP, и иначе разрешимы за (скажем) времени?O(2n)O(2n)O(2^n) Простым примером может быть: Если P! = NP, вычислите тест на простоту для случайного n-разрядного числа, в противном случае оцените случайную позицию...
Используя модель real-RAM / BSS, мы имеем класс NP (где BSS - это модель компьютера Блума-Шуб-Смейла с операциями над реалами). У нас есть NP полные проблемы. Итак, вопрос в том, существует ли аналог гипотезы Бермана Хартманиса для класса NP ? Конечно, поставленный здесь вопрос зависит от модели -...