NP полнота над реалами

13

Недавно я изучаю модель вычисления BSS (см., Например, Сложность и Реальные вычисления; Блум, Кукер, Шуб, Смейл.)

Для вещественных чисел показано, что для заданной системы полиномов f 1 , , f mR [ x 1 , , x n ] существование нулей является N P R -полным. Однако мне интересно, если эти f являются полиномами, имеют только целые коэффициенты, то есть f 1 , , f mZ [ x 1 , , x n ]Rf1,,fmR[x1,,xn]NPRff1,,fmZ[x1,,xn], все еще проблема -hard? (это очевидно в N P R ).NPRNPR

Я подозреваю, да, но есть ли простое доказательство?

Maomao
источник

Ответы:

3

Я думаю, что ответ « нет» , если предположить, что (я полагаю, что я приведу доказательство ниже, но здесь есть достаточно потенциально придирчивые проблемы с определениями, поэтому я осторожно отношусь к своим утверждениям).PRNPR

Доказательство того, что ответ не предполагает PRNPR : На самом деле, я считаю, что имеет место следующее более сильное утверждение:

Лемма: Для любого решения задачи ПБСА над R , если L поли-время ПБС R сводится к задаче о целочисленных входах, то L P R .LRLRLPR

Доказательство леммы : Предположим , что были полиномиальное время ПБС R сокращение по сравнению с L к задаче о целочисленных входов, задается машиной М . Для входных данных, состоящих из n действительных параметров, разверните вычисление M в алгебраическое дерево вычислений. Существует только конечное число листов, и результат на каждом листе является единственной рациональной функцией во входных параметрах. Чтобы рациональная функция реальных входных данных всегда выводила целочисленное значение, она должна быть постоянной функцией и поэтому не зависеть от входных данных. Однако то, какая постоянная функция используется на каждом листе, может, конечно, зависеть от ветвей. Тем не менее, так как М является однородной машиной, может быть только ОRLMnMM выходные узлы и, следовательно, только O ( 1 ) выходные значения. Таким образом, M можно тривиально изменить, чтобы фактически решить L за полиномиальное время. QEDO(1)O(1)ML

Теперь возьмем чтобы быть реальным осуществимость реальных полиномов. Если P RN P R , то L P R , и по лемме нет сокращения от L до любой задачи на целочисленных входах (в частности, к реальной выполнимости целочисленных полиномов).LPRNPRLPRL

Обещать проблему вопросом? : Другая потенциальная проблема с вашим вопросом заключается в том, что реальная выполнимость целочисленных полиномов может быть не в NPR , а только в его обещающей версии. Проблема здесь заключается в том, что для проверки того, что вход (например, коэффициент многочлена ) является целым числом, требуется время, которое зависит от величины x , тогда как набор экземпляров (все экземпляры, а не только yes-экземпляры) для N P R проблема решения должна быть разрешимой в P R , в последнем смысле , что она занимает полиномиальное время в ряде параметровfixNPRPRа не их величины. Это, я полагаю, тесно связано с тем фактом, что целые числа не могут быть определены в первом порядке в действительных числах. (По сути, лучшее, что может сделать машина BSS R для проверки, является ли вход x целым числом, - это вычислить целую часть x с помощью вычисления степеней 2 и выполнения «двоичного поиска». Как только он вычислил целую часть x , он просто проверяет, равно ли это x .) Так что я думаю, что проблема реальной выполнимости целочисленных уравнений в P r o m i s e N P R, но, вероятно, не в NRxx2xxPromiseNPR (или, по крайней мере, кажется нетривиальным доказать, что он находится в N P R ).NPRNPR

Джошуа Грохов
источник