пропозициональные системы доказательства и соответствующие ограниченные арифметические теории
Этот вопрос вдохновлен аналогичным вопросом о прикладной математике на mathoverflow, и что ноющая мысль, что важные вопросы TCS, такие как P против NP, могут быть независимыми от ZFC (или других систем). В качестве небольшого фона обратная математика - это проект поиска аксиом, необходимых для...
Это наивный вопрос, из моего опыта; заранее извиняюсь. Гипотеза Гольдбаха и многие другие нерешенные вопросы математики могут быть записаны в виде кратких формул в исчислении предикатов. Например, статья Кука "Могут ли компьютеры регулярно находить математические доказательства?" формулирует эту...
Вопрос о теории « Что такое NP, ограниченный свидетелями линейного размера? », Задает вопрос о классе NP, ограниченном свидетелями линейного размера , ноO(n)O(n)O(n) Существуют ли естественные NP-полные проблемы, в которых (да) экземпляры размера требуют свидетелей размером больше ?нnnnnnn...
Вы можете часто находить методы разрезающих плоскостей, переменное распространение, ветвление и связывание, обучение по пунктам, интеллектуальное возвращение в исходное положение или даже эвристику человека, сплетенную вручную, в решениях SAT. Тем не менее, на протяжении десятилетий лучшие SAT...
Недавно я видел несколько статей об arxiv, которые ссылаются на систему доказательств под названием сумма квадратов. Может кто-нибудь объяснить, что такое доказательство суммы квадратов и почему такие доказательства важны / интересны? Как они связаны с другими алгебраическими системами...
Есть ли обзор алгоритмов вычисления интерполантов? Как насчет работ только по одному алгоритму? Случай я больше всего интересует = ¬ р ∧ д и С = д , а также ограничение , что интерполянт настолько мал , насколько это возможно. (Мне известна статья Макмиллана 2005 года , в которой описывается, как...
XORification - это метод усложнения булевой функции или формулы путем замены каждой переменной на XOR k ≥ 2 различных переменных x 1 ⊕ … ⊕ x k . xxxk≥2k≥2k\geq 2x1⊕…⊕xkx1⊕…⊕xkx_1 \oplus \ldots \oplus x_k Мне известно об использовании этого метода для усложнения доказательства, главным образом для...
Я ищу естественные примеры эффективных алгоритмов (т.е. в полиномиальном времени) их правильность и эффективность могут быть доказаны конструктивно (например, в PRAпрAPRA или ), ноHAЧАСAHA не известно никаких доказательств, использующих только эффективные концепции (то есть мы не знаем, как...
Читая статью « Аппликативная теория для FPH », вы можете встретить следующий отрывок: Рассматривая теории, которые характеризуют классы вычислительной сложности, существует три разных подхода: в одном функции, которые могут быть определены в рамках теории, «автоматически» находятся в определенном...
Мы знаем, что основанные на DPLL SAT-решатели не могут правильно ответить на неудовлетворительных экземплярах (принцип "голубиной дыры"), например, "существует инъективное отображение от к ": n + 1 nP H PPHP\mathrm{PHP}n + 1n+1n+1Nnn P H Pn + 1N: = ⎛⎝⋀i ∈ [ n + 1 ] ⋁j ∈ [ n ] пя , дж⎞⎠∧ ⎛⎝⋀я ≠ я'∈...
Этот вопрос касается логики высказываний, и все случаи «разрешения» следует понимать как «предложенные решения». Этот вопрос является чем-то чрезвычайно основным, но это беспокоило меня некоторое время. Я вижу, как люди утверждают, что решение по предложению завершено, но я также вижу, что люди...
Были бы какие-нибудь серьезные последствия, если бы у SAT было самое большее субэкспоненциальное несогласованное доказательство или даже более сильно, у SAT были алгоритмы субэкспоненциального...
Если предположить, что NP! = CoNP, то для проблемы полного завершения coNP нет сертификата полиномиального размера. Но как насчет субэкспоненциального размера сертификата? Особенно для coSAT, есть ли субэкспоненциальное доказательство размера, чтобы доказать, что формула неудовлетворительна? Если...
Напомним , что ширина резолюции опровержение RRR из формулы CNF FFF представляет максимальное число литералов в любом пункте , происходящих в RRR . Для каждого в 3-CNF wwwесть неудовлетворительные формулы FFF каждое опровержение разрешения FFF требует ширины не менее www . Мне нужен конкретный...
Недавно я начал много читать о сложности доказательств, и мне очень понравилось то, что я читал. Я действительно хотел бы узнать больше об этом, но мне трудно найти хороший материал для начинающих. Кто-нибудь сможет порекомендовать некоторые...
Предположим, что NP = co-NP, а полином ограничивает длину доказательства неудовлетворенности для экземпляра 3-CNF x . Тогда есть ли какие-либо результаты о том, в какой форме может быть получено любое доказательство неудовлетворенности для x длины ≤ p ( x ) ? Т.е. в целом, должно ли такое...
Мотивация для этого вопроса - факт, что большинство n-битных строк несжимаемо. Интуитивно, мы можем предложить по аналогии, что большинство доказательств тавтологии несжимаемы до полиномиального размера. По сути, моя интуиция заключается в том, что некоторые доказательства по своей природе случайны...
Резолюция - это схема, доказывающая неудовлетворенность CNF. Доказательством в резолюции является логический вывод пустого предложения для начальных предложений в CNF. В частности, любой начальный пункт может быть выведен, и из двух пунктов и B ∨ ¬ x также может быть выведен пункт A ∨ B....
В разговоре Разборова опубликовано любопытное небольшое заявление. Если ФАКТОРИНГ труден, то маленькая теорема Ферма не доказуема в .S12S21S_{2}^{1} Что такое и почему текущих доказательств нет в ? S 1...
Существует ли естественный класс формул CNF - предпочтительно тот, который ранее изучался в литературе - со следующими свойствами:CCC является простым случаем SAT, как, например, Horn или 2-CNF, т. Е. Членство в C можно проверить за полиномиальное время, а формулы F ∈ C можно проверить на...