Что именно означает «Расширение полинома»?

Это из рукописи книги о доказательствах с нулевым разглашением - https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

3.5 Низкостепенные и полилинейные расширения Let $\mathbb F$ — любое конечное поле, и пусть $f : \{0, 1\}^v \стрелка вправо \mathbb F$ быть любым функция, отображающая v-мерный булев гиперкуб в $\mathbb F$. А $v$полиномиальная переменная $г$ над $\mathbb F$ говорят, что это расширение из $f$ если $г$ согласуется со всеми булевыми входными данными, т. е. $ г (х) = ф(х)$ для всех $x \in \{0, 1\}^v$

Я не могу понять, что это значит.

• Я не думаю, что они говорят здесь о полях расширения - т.е. тогда они бы $\mathbb F_p$ & $\mathbb F_{p^n}$

• Я думаю $\{0,1\}^v$ это битовая строка $v$ биты. Или я неверно истолковываю?

• $f$ это карта - однако я думаю, что это также многочлен. Это, вероятно, в виде многочлена максимальной степени $v$ & он берет свои коэффициенты из $\mathbb F_2$.

• И $г$ другой полином. Однако мне не ясно, какое поле $г$ берет свой коэффициент из.

• $г$ это $v$ переменный полином. Так что именно делает $f(х) = г(х)$ для всех $x \in \{0, 1\}^v$ иметь в виду. Если $г$ является многомерным полиномом, то g нельзя вычислить только с помощью $х$ как вход - это нужно $v$ различные переменные для оценки, т.е. $г(х_1, х_2 .... х_в)$. Итак, как у нас есть $f(х) = г(х)$?

Я вообще не понимаю, что это за "Расширение полинома"? Может ли кто-нибудь помочь мне понять, что означает цитируемое определение.

Возможно, более известное название этой техники арифметизация. Общая идея, лежащая в основе этого, состоит в том, чтобы закодировать логическую логику в полиномы низкой степени, которые (по определенным техническим причинам) имеют различные доступные аналитические методы (вероятно, наиболее очевидным является лемма Шварца-Циппеля). Это особенно полезно для доказательства надежности интерактивных доказательств и было ключом к доказательству Шамира $\mathsf{IP} = \mathsf{PSPACE}$.

$f$ это карта - однако я думаю, что это также многочлен. Это, вероятно, в виде многочлена максимальной степени $v$ & он берет свои коэффициенты из $\mathbb{F}_2$.

Даже если вы можете думать о $f$ как многочлен, лучше не делать этого. У нас есть некоторый исходный «стандартный» вычислительный объект, который мы хотим проанализировать, что обычно означает

• логическая формула или
• логическая схема или
• таблица истинности.

Вы можете просмотреть все это как многочлены по $\mathbb{F}_2$ (и, возможно, это именно то, чем являются логические схемы), но иногда вместо этого у вас будет формула или что-то еще.

Идея поиска полинома расширения (или, как я уже говорил, обращения к «арифметизации») состоит в том, чтобы закодировать этот (стандартный) объект как полином $g(x) \in \mathbb{F}[x_1,\dots,x_v]$ что "согласен с" $ф(х)$ в том смысле, что

$$\forall (x_1,\dots,x_v)\in\{0,1\}^v : f(x_1,\dots,x_v) = g(x_1,\dots,x_v).$$

Это можно легко сделать для определенных операций, например $g_{И}(х,у) = ху$ является расширением И, $g_{НЕ}(х) = 1-х$ является расширением НЕ. Для других операций это немного менее просто, например $$g_{XOR}(x,y) = x+y-2xy = 1 - (xy - (1-x)(1-y)).$$ является арифметизацией XOR (я думаю) и, возможно, заранее не очевиден.

В комментариях вы спрашивали, почему нас это волнует. Возможно, наилучшей мотивацией является лемма Шварца-Циппеля, но ее техническая лемма о полезности может оказаться полезной не сразу. «Высота высоты» для арифметизации

1. это было ключом к доказательству $\mathsf{IP} = \mathsf{PSPACE}$ (через протокол "sumcheck" Шамира), один из первых больших результатов в системах интерактивных доказательств, и
2. доказательство этого результата было особый (нерелятивистское, а не естественное доказательство). Возможно, «арифметизация» является одним из ~ 3 или 4 фундаментальных методов доказательства, известных нам в теории сложности. До 2009 года это были действительно основные «большие» техники, которые еще могли показать, что $\mathsf{P} \neq \mathsf{NP}$ --- у него больше нет выстрела.

Во всяком случае, для явной ссылки на книгу я знаю, что она, по крайней мере, содержится в книге Ароры и Барака. Вычислительная сложность: современный подход. Использование Ctrl+F для поиска «арифметизации» сразу же приведет вас к главе 8.5.2, в которой обсуждается этот подход. В общем, поиск по этому термину, вероятно, будет гораздо более плодотворным, чем поиск по «полиномиальному расширению», который может иметь больше непреднамеренных коллизий имен.