Изложение результата Baker-Gill-Solovay 1975 о релятивизации P vs NP

ru · unofficial · sha256:e2a60e21e70f57cf66c7c5ea580c79b01ff252c7d414e9b62bfd4152a33a7eb4

Изложение результата Baker, Gill, Solovay (1975) о релятивизации вопроса P vs NP Это АВТОРСКОЕ ИЗЛОЖЕНИЕ (sourceFidelity = "authored_exposition"), написанное для настоящего репозитория, а не перепечатка или перевод статьи. Сама статья — T. Baker, J. Gill, R. Solovay, "Relativizations of the P =? NP Question", SIAM Journal on Computing, vol. 4, no. 4, pp. 431-442, 1975 — защищена авторским правом и в воспроизводимом виде не пинуется; её существование и локатор называются как reference-факт этого изложения, по образцу corpus/laws/doctrine/cs/description (logic/zebra, faraid.shares). Результат. Оракульная машина Тьюринга получает бесплатный доступ к множеству-оракулу O: за один шаг она узнаёт, лежит ли строка в O. P^O и NP^O — релятивизации классов P и NP относительно оракула O: класс языков, разрешимых (соответственно, недетерминированно проверяемых) за полиномиальное время машиной с оракулом O. Доказательство МЕТОДОМ РЕЛЯТИВИЗУЕТСЯ, если его рассуждение работает без изменений для машин с произвольным фиксированным оракулом O — то есть доказывает утверждение не только о P и NP, но и о P^O и NP^O для любого O одновременно. Главный результат статьи: существует оракул A такой, что P^A = NP^A, и существует оракул B такой, что P^B ≠ NP^B. Поскольку релятивизующее доказательство P = NP автоматически доказало бы и P^B = NP^B (что ложно для оракула B), а релятивизующее доказательство P ≠ NP автоматически доказало бы и P^A ≠ NP^A (что ложно для оракула A) — НИ P = NP, НИ P ≠ NP не может быть доказано методом, который релятивизуется. Это утверждение о ГРАНИЦЕ КЛАССА МЕТОДОВ (какие методы годятся, в принципе), а не ответ на сам вопрос P vs NP и не факт о том, что вопрос неразрешим: методы, не релятивизующиеся (например, диагонализация с использованием булевых схем, интерактивных доказательств — впоследствии IP = PSPACE, доказанное именно нерелятивизующимся методом), барьером не затронуты. reference: Baker, Gill, Solovay, "Relativizations of the P =? NP Question", SIAM J. Computing 4(4):431-442, 1975, Theorem (existence of oracles A, B).

Ссылаются нормы: BgsClaim, BgsProof, BgsSource, NonRelativizingTechnique, Oracle, OracleA, OracleB, RelativizationBarrier, RelativizingMethod, SimpleDiagonalization, bgs-proves, diagonalization-relativizes, oracle-a-collapses, oracle-b-separates, oracle_collapses_p_np, oracle_separates_p_np, relativization_barrier_applies, relativizes