Многие считают, что . Однако мы только знаем, что находится на втором уровне полиномиальной иерархии, то есть . Шаг к показу состоит в том, чтобы сначала перевести его на первый уровень полиномиальной иерархии, то есть .BPPPNPBPP=P⊆NP\mathsf{BPP} = \mathsf{P} \subseteq...
Существуют ли какие-нибудь игрушечные примеры, которые дают «существенную» информацию для понимания трех известных барьеров для проблемы P=NPP=NPP = NP - релятивизации, естественных доказательств и...
Хорошо известно, что любое доказательство, решающее вопрос P против NP, должно преодолевать релятивизацию , естественные доказательства и барьеры алгебраизации . Следующая диаграмма разбивает «пространство доказательств» на различные области. Например, соответствует набору доказательств, которые...
Недавно Райан Уилламс доказал, что конструктивность в естественном доказательстве неизбежно приводит к разделению классов сложности: и . N E X PNЕИксп\mathsf{NEXP}Т С0TС0\mathsf{TC}^{0} Конструктивность в естественном доказательстве - это условие, которому удовлетворяют все комбинаторные...
Точная формулировка названия принадлежит Ананду Кулькарни (который предложил создать этот сайт). Этот вопрос был задан в качестве примера вопроса, но мне безумно любопытно. Я очень мало знаю об алгебраической геометрии, и на самом деле у меня есть только беглое понимание студентами препятствий,...
Естественное доказательство является препятствием для доказательства нижних оценок сложности схемы булевых функций. Они напрямую не подразумевают такого барьера в доказательстве нижних границ сложности схемы. Есть ли прогресс в выявлении таких барьеров? Есть ли другие барьеры в монотонной...
Мы все знаем, что у есть барьеры. Мы все изучили эти барьеры, потому что мы считаем, что .P ≠ N Pп≠ NпP≠NPP\ne NPп≠ NпP≠NPP\ne NP Однако предположим, что и есть мудрые люди, которые считают, что такая возможность существует . Если это действительно так, то сам факт того, что мы не видели хороших...
Я не помню, чтобы видел разделение классов, не основанное на диагонализации и результатах релятивизации. Диагонализация все еще может использоваться для разделения оставшихся известных классов, потому что нерелятивизирующие аргументы могут все еще использоваться в заключении диагонализации или в...
Это продолжение моего предыдущего вопроса: Лучшая известная нижняя оценка сложности времени для естественной задачи в NP Я нахожу удивительным, что мы не смогли доказать какую-либо квадратичную детерминированную нижнюю границу для любой интересной проблемы NP, которая интересует людей и пытается...
Влияет ли естественное доказательство , релятивизация и алгебризация на разделение других классов сложности, таких как т. Д.?L≠NL≠NP≠coNP≠PH≠PSPACEL≠NL≠NP≠coNP≠PH≠PSPACEL\neq NL\neq NP\neq coNP \neq PH\neq PSPACE Например, барьер естественных доказательств должен влиять на любое доказательство...