Барьер релятивизации: почему сложно разрешить противопоставление P и NP.

В 1975 году Бейкер, Гилл и Соловай доказали, что самый мощный метод в теории сложности не может разрешить противоречие между P и NP. Этот метод — диагонализация, тот же самый метод, который разделил временные классы, пространственные классы и провел все четкие границы в этой области до этого момента. Проблема в том, что диагонализация рассматривает машину как черный ящик. Бейкер, Гилл и Соловай построили два оракулы: один, который делает P равным NP, и другой, который их разделяет. Мы утверждаем, что любое доказательство, работающее одинаково независимо от выбора оракула, релятивизирует. Из-за оракулов Бейкера, Гилла и Соловая любое доказательство, разрешающее вопрос P против NP и релятивизирующее его, должно приводить к противоречию в одном из двух миров. Это означает, что прямая диагонализация не сработает. В этом видео подробно рассматривается доказательство теоремы о временной иерархии методом диагонализации, определяются оракульные машины Тьюринга и релятивизированные классы сложности, подробно строятся оба типа оракулов и объясняется, почему диагонализация и другие релятивизирующие методы заблокированы. Сопутствующая статья: https://computablesecrets.com/videos/.... Если вы хотите поддержать эту работу, пожалуйста, оформите членство на моем сайте: https://computablesecrets.com. Список литературы: «Релятивизация вопроса P = ? NP» Т. Бейкера, Дж. Гилла и Р. Соловая (1975) «Относительно случайного оракула A, P^A != NP^A != coNP^A с вероятностью 1» К. Беннетта и Дж. Гилла (1981) «Роль релятивизации в теории сложности» Л. Фортноу (1994) «IP = PSPACE» А. Шамира (1992) «Алгебризация: новый барьер в теории сложности» С. Ааронсона и А. Вигдерсона (2009) «Введение в теорию вычислений» М. Сипсера (2013) «Вычислительная сложность: современный подход» С. Ароры и Б. Барака (2009) Manim (библиотека Python для визуализации) Клод Код (помощь в редактировании и производстве)