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

Доказательство сложности является основной областью теории вычислительной сложности. Конечная цель этой области состоит в том, чтобы доказать , то есть любой доказатель не может дать доказательство неудовлетворенности данной входной формулой. Nп≠ c o NпNп≠соNпNP\neq coNP Граф - это одна из...

Я пытаюсь понять статью о p-оптимальных системах доказательства и логике для PTIME . В статье есть понятие, называемое системами доказательства, и я не понимаю интуиции: Σ = { 0 , 1 }Σ={0,1}\Sigma = \{0,1\} ... Мы выявляем проблемы с подмножествами QQQ в Σ*Σ∗\Sigma^*, Я думаю, что интуиция...

Википедия [1] утверждает, что наиболее известная нижняя оценка размера доказательств Фреге является квадратичной, и что нет известных суперлинейных нижних оценок для числа линий доказательств Фреге. Вопросов: 1) Какова наиболее известная нижняя граница для числа строк расширенных доказательств...