Вопросы с тегом «proof-search»

Если P = NP, можем ли мы получить доказательства гипотезы Гольдбаха и т. Д.?

Это наивный вопрос, из моего опыта; заранее извиняюсь. Гипотеза Гольдбаха и многие другие нерешенные вопросы математики могут быть записаны в виде кратких формул в исчислении предикатов. Например, статья Кука "Могут ли компьютеры регулярно находить математические доказательства?" формулирует эту...

Теорема о прямой сумме для пространственной сложности предложения Резолюции?

Резолюция - это схема, доказывающая неудовлетворенность CNF. Доказательством в резолюции является логический вывод пустого предложения для начальных предложений в CNF. В частности, любой начальный пункт может быть выведен, и из двух пунктов и B ∨ ¬ x также может быть выведен пункт A ∨ B....