Барьер естественных доказательств

В 1994 году Разборов и Рудич показали, что все известные методы доказательства нижних границ схем имеют общую структуру, которую они назвали естественным доказательством. Более того, они показали, что естественные доказательства принципиально противоречат мощным классам схем. Если псевдослучайные функции существуют, то никакое естественное доказательство не может показать, что SAT требует суперполиномиальных схем. Таким образом, та самая сложность, которую мы хотели доказать, скрывала проблему от нашего прогресса с помощью методов, известных на момент написания их работы. Сопутствующая статья: https://computablesecrets.com/videos/.... Если вы хотите поддержать эту работу, пожалуйста, оформите членство на моем сайте: https://computablesecrets.com. Источники: «Естественные доказательства» А. А. Разборова и С. Рудича (1997) «Нижние границы неравномерных цепей ACC» Р. Уильямса (2014) «Естественные доказательства против дерандомизации» Р. Уильямса (2016) «Как построить случайные функции» О. Голдрейха, С. Голдвассера и С. Микали (1986) «Релятивизация вопроса P = ? NP» Т. Бейкера, Дж. Гилла и Р. Соловая (1975) Manim (библиотека Python для визуализации) Клод Код (помощь в редактировании и производстве)