Уловка, использованная в доказательстве двукратно экспоненциальной сложности арифметики Пресбургера

Я разместил это на MathUnderflow, но не получил ответов, поэтому решил попробовать здесь,

Я читаю старую статью Рабина и Фишера [опубликует ссылку, когда это возможно], где, помимо прочего, доказана двоякая экспоненциальная сложность арифметики Пресбургера.

Доказательство основывается на существовании формулы неформально утверждающей « » с . Хотя конструкция этой формулы не приведена в статье, что меня удивило, учитывая, что она предположительно весьма нетривиальна, учитывая эту границу и тот факт, что в нашем распоряжении есть только сложение! $I_{n}(x)$ $x < 2^{2^{kx+1}}$ $|I_{n}| \in O(n)$

Позже я узнал, что построение этой формулы опирается на «уловку», ранее обнаруженную Фишером, и независимо от Фолькера Штрассена, но мне не удалось отследить статью, подробно описывающую эту уловку!

Так что, если кто-то знает о бумаге, о которой я говорю, и может либо указать мне ее направление, либо даже описать мне трюк ...

Этот пост из блога Липтона содержит ссылку на статью, а также упоминает [и предоставляет грубый, к сожалению, недостаточный для меня, набросок] упомянутого трюка, кстати.

Я знаю, что это расплывчатое описание. Хотя достаточно подробное описание было бы слишком длинным для поста SX, так что я просто надеюсь, что кто-то, кто уже знает об этой статье - и, следовательно, сможет справиться с этим кратким наброском, - натолкнется на это и сможет мне помочь. ,

complexity-theory reference-request logic мокрый
источник

n

$n$

k

$k$

2^{2^{n x + 1}}

$2^{2^{nx+1}}$

Вы можете скачать статью о Фишере и Рабине здесь .

Мартин Бергер

Строительство будет дано в работе: Теорема 8 на страницах 14-15 (фактическое утверждение следствия 9 на странице 16).

Юваль Фильмус

Комментарий Мартина (и продолжение Ювала) дает ссылку, которая объясняет конструкцию в некоторых деталях.

$2^{2^{c\cdot n}}$ $M_n(x,y,z)$

M_{N} (Икс, Y, Z) \Leftrightarrow Икс \times Y знак равно Z \land Икс < 2^{2^{N}}

$M_n(x,y,z) \Leftrightarrow x\times y=z\ \wedge x< 2^{2^n}$

$M_n$ $n$

$M_{n+1}(x,y,z)$

M_{N} ({Икс}_{1}, Y_{1}, Z_{1}) \land M_{N} ({Икс}_{2}, Y_{2}, Z_{2}) \land M_{N} ({Икс}_{3}, Y_{3}, Z_{3})

$M_{n}(x_1,y_1,z_1)\wedge M_{n}(x_2,y_2,z_2)\wedge M_{n}(x_3,y_3,z_3)$

\forall U v вес, (U знак равно {Икс}_{1} \land v знак равно Y_{1} \land вес знак равно Z_{1}) \lor (U знак равно {Икс}_{2} \land v знак равно Y_{2} \land вес знак равно Z_{2}) \lor (U знак равно {Икс}_{3} \land v знак равно Y_{3} \land вес знак равно Z_{3}) \Rightarrow M_{N} (U, v, вес)

$\forall u v w,(u=x_1\wedge v=y_1\wedge w=z_1)\vee(u=x_2\wedge v=y_2\wedge w=z_2)\vee(u=x_3\wedge v=y_3\wedge w=z_3)\Rightarrow M_n(u,v,w)$

$n$

Есть несколько других трюков, но это основной. Конечно, внутренности рекурсии важны, но сходство с трюком Карацубы действительно поразительно.

Коди
источник

P S P A C E = N P S P A C E

$PSPACE=NPSPACE$

Уловка, использованная в доказательстве двукратно экспоненциальной сложности арифметики Пресбургера

Ответы: