РЕДАКТИРОВАТЬ в 2011/02/08: После того, как некоторые ссылки были найдены и прочитаны, я решил разделить оригинальный вопрос на два отдельных. Вот часть, касающаяся UP vs NP, для части синтаксических и семантических классов см. Преимущества для синтаксических и семантических классов ....
Недавно Ватроус и др. Доказали, что QIP (3) = PSPACE - замечательный результат. Это был удивительный результат для меня, если не сказать больше, и это заставило меня задуматься ... Я задавался вопросом, что если бы Quantum Computers могла эффективно моделироваться классическими компьютерами. Может...
Следуя предложению Джоша Грохова, я превращаю свой комментарий из предыдущего вопроса в новый. Какие доказательства у нас есть для ?UP≠NPUP≠NP\mathsf{UP} \neq \mathsf{NP} Здесь - это класс языков, распознаваемых недетерминированными машинами Тьюринга за полиномиальное время, которые имеют...
В нашей недавней работе мы решили вычислительную проблему, возникшую в комбинаторном контексте, исходя из предположения, что , где - это -версия . Единственной найденной нами статьей о была статья Бейгеля-Бурмана-Фортнау 1998 года , в которой упоминается комплексный зоопарк . Мы понимаем, что можем...
Недавний вопрос (см Последствия 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...
Мы знаем, что если то весь PH разрушается. Что если полиномиальная иерархия частично разрушится? (Или как понять, что PH может рухнуть выше определенной точки, а не ниже?)п= NпP=NPP=NP Короче говоря, каковы будут последствия и P ≠ N P ?Nп= с о нпNP=coNPNP=coNPп≠ NпP≠NPP\ne...
широко предположительно, чтобы быть ложным.R P= NпRP=NPRP = NP Но представьте на мгновение, что это правда. В таком случае, насколько вероятно, что ?п= NпP=NPP = NP Другими словами: в мире, где , что еще может помешать нам верить P = N P ?R P= NпRP=NPRP = NPп= NпP=NPP =...
P/poly=NP/polyP/poly=NP/polyP/poly = NP/poly означает , что, в свою очередь, имеет интересные последствия, такие как коллапс полиномиальной иерархии.NP⊆P/polyNP⊆P/polyNP \subseteq P/poly Есть ли интересные последствия для ?P/poly≠NP/polyP/poly≠NP/polyP/poly \neq...
в 1979 году Хопкрофт / Ульман написал, что L ⊆ P ⊆ NP ⊆ PSpace известно, но L ⊊ PSpace является единственным известным (и тривиальным) сдерживанием, известным, хотя все предполагаются как надлежащие сдерживания, и «где вещи все еще стоят» ~ 4 десятилетия спустя , с тех пор существует ли какая-либо...
Учитывая , таким образом, что коэффициенты р , д ограничены B , имеет р ≡ Q удержание ?p(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x_1,\dots,x_n),q(x_1,\dots,x_n)\in \Bbb Z[x_1,\dots,x_n]p,qp,qp,qBBBp≡qp≡qp\equiv q Здесь применима лемма Шварца-Циппеля, поскольку она...
Имеет ли означают E = N E