Изложение результата Razborov-Rudich 1994/1997 о natural proofs

ru · unofficial · sha256:2fd8d95b6aee05b282c1fa4fa787e342dad432e9a91336d58101884907517511

Изложение результата Razborov, Rudich (1994/1997) о natural proofs Это АВТОРСКОЕ ИЗЛОЖЕНИЕ (sourceFidelity = "authored_exposition"), написанное для настоящего репозитория, а не перепечатка или перевод статьи. Сама статья — A. Razborov, S. Rudich, "Natural Proofs", Journal of Computer and System Sciences 55(1):24-35, 1997 (доклад — STOC 1994) — защищена авторским правом и в воспроизводимом виде не пинуется; её существование и локатор называются как reference-факт этого изложения, по образцу corpus/laws/doctrine/cs/description. Результат. "Естественное доказательство" (natural proof) нижней оценки сложности схем для булевой функции f обладает двумя свойствами разом: конструктивность (constructivity) — свойство схем C, на которых доказательство строит оценку, распознаётся за время, полиномиальное от размера таблицы истинности входа; крупность (largeness) — доля входов, обладающих этим свойством, среди всех булевых функций данной арности не исчезающе мала (не менее 1/2^{O(n)} по стандартной нормировке статьи). Почти все известные на 1994 год доказательства нижних оценок для немонотонных схемных моделей (Разборов-Смоленский, Furst-Saxe-Sipser, Yao, Håstad и другие) подпадают под это определение. Главный результат: ЕСЛИ существуют достаточно сильные (криптографически стойкие) псевдослучайные генераторы (условие — существование однонаправленных функций экспоненциальной стойкости), ТО никакое естественное доказательство не может дать сверхполиномиальную нижнюю оценку сложности схем общего вида — естественное доказательство отличало бы выход генератора от случайной строки, что противоречит псевдослучайности. Это УСЛОВНЫЙ барьер: без допущения о существовании таких генераторов статья доказывает более слабое безусловное утверждение — естественные доказательства не могут дать экспоненциальную нижнюю оценку для задачи дискретного логарифма. Условность обязана кодироваться явно (conditional_on/assumed_in_scenario, контракт arxo.math_claims), не как безусловный барьер на весь класс методов. reference: Razborov, Rudich, "Natural Proofs", J. Comput. Syst. Sci. 55(1):24-35, 1997 (STOC 1994), Main Theorem (natural proofs vs pseudorandom function generators).

Ссылаются нормы: BoundProofAttempt, DiscreteLogBarrierClaim, DiscreteLogUnconditionalProof, IsNaturalProofRequiresBoth, NaturalProofsBarrierClaim, NaturalProofsUnconditionalProof, RRSource, RazborovSmolenskyStyleAttempt, StrongPrgExistenceClaim, is_constructive, is_large, is_natural_proof, rr-conditional, rr-proves-discrete-log, rs-attempt-constructive, rs-attempt-large