Существуют ли классы сложности с действительными числами?

14

Один студент недавно попросил меня проверить доказательство твердости NP для них. Они выполнили сокращение в соответствии с:

Я уменьшаю эту проблему п' которая, как известно, является NP-полной, к моей проблеме (с многократным уменьшением многократного числа), поэтому является NP-трудной.пп

Мой ответ был в основном:

Поскольку у есть экземпляры со значениями из , он тривиально не вычисляется по Тьюрингу, поэтому вы можете пропустить сокращение.пр

Хотя формально это правда, я не думаю, что этот подход является проницательным: мы, безусловно, хотели бы иметь возможность уловить «присущую сложность» реальной задачи решения (или оптимизации), игнорируя ограничения, с которыми мы сталкиваемся при работе с реальной числа; расследование этих вопросов еще на один день.

Конечно, это не всегда так просто, как сказать: «Дискретная версия Subset Sum является NP-полной, поэтому непрерывная версия также« NP-hard »также». В этом случае сокращение легко, но есть известные случаи упрощения непрерывной версии, например, линейное или целочисленное программирование.

Мне пришло в голову, что модель RAM естественно распространяется на реальные числа; пусть каждый регистр хранит действительное число и соответственно расширяет основные операции. Модель равномерной стоимости все еще имеет смысл - так же, как и в дискретном случае, в то время как логарифмическая - нет.

Итак, мой вопрос сводится к следующему: существуют ли устоявшиеся представления о сложности реальных задач? Как они относятся к «стандартным» дискретным классам?

Поиски в Google дают некоторые результаты, например, это , но я не могу сказать, что установлено и / или полезно, а что нет.

Рафаэль
источник
1
Вы можете найти интересные «Сложность и реальные вычисления» amazon.com/Complexity-Real-Computation-Lenore-Blum/dp/…
Курт Мюллер,
Мне кажется, что ваш ответ вашему ученику был необоснованным по одной простой причине: какие бы вычисления мы ни использовали, чтобы рассматривать их как основанные на реалах, можно также проводить с использованием вычислимых реалов . Я не знаю, является ли этот ответ пригодным для целей вашего ученика, но он должен по крайней мере покончить с отсутствием аргумента вычислимости Тьюринга. К сожалению, я недостаточно разбираюсь в этих вопросах, чтобы развивать это дальше.
Бабу
@babou Что касается вычислимости, то это может быть разумным ограничением (но, тем не менее, им придется заявить!). Однако что происходит со сложностью?
Рафаэль
@ Рафаэль Моя точка зрения на самом деле, что это даже не ограничение, и не нужно указывать. Это просто неизбежно. Единственными действительными значениями, которые вы можете учитывать при вычислении, являются вычислимые действительные значения (тезис Черча-Тьюринга). Хорошая часть, по-видимому, заключается в том, что она не меняет ни одной соответствующей математики с должной тщательностью. Выход за пределы вычислимых реалов, как использование более высоких уровней иерархии Тьюринга, увлекательная спекуляция, вероятно, мало влияющая на что-либо реальное (каламбур неизбежен).
Бабу

Ответы:

8

Да. Есть.

В другом ответе упоминается модель real-RAM / BSS. У модели есть некоторые проблемы, и AFAIK не так много исследований по этому поводу. Возможно, это не реалистичная модель вычислений .

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

Исследование сложности функций высшего типа восходит, по крайней мере, к [1]. Для недавней работы проверьте статьи Акитоши Кавамуры о сложности реальных операторов.

Классическим справочником по сложности вещественных функций является книга Кер-Ко Ко [2]. В шестой главе более поздней книги Клауса Вейрауха [3] также обсуждается сложность реальных вычислений (но она больше сфокусирована на вычислимости, чем на сложности).

  • [1] Стивен Кук и Брюс Капрон, "Характеристики основных выполнимых функционалов конечного типа", 1990.

  • [2] Кер-И Ко, "Вычислительная сложность вещественных функций", 1991.

  • [3] Клаус Вейраух «Вычислительный анализ», 2000.

Кава
источник
Что делает функциональную модель более высокого типа более реалистичной, чем реальная модель ОЗУ?
Рафаэль
1
@ Рафаэль, кажется, я объяснил это в связанном вопросе. Если вы хотите больше через лечение, есть несколько, одна из них - глава 9 Weirauch. Еще одна хорошая статья IIRC - статья Такера и Столенберга-Хансена.
Каве
1
На мой взгляд, модель реальной оперативной памяти имеет две основные проблемы: с одной стороны, ей не хватает понятия произвольной точности рациональной аппроксимации действительных чисел, что, возможно, является их основным свойством, с другой стороны, она позволяет сравнивать действительные числа, которых AFAIK никто не знает как делать на практике. В результате некоторые реальные функции, которые мы считаем эффективно вычислимыми на практике, не вычислимы в модели, в то время как некоторые эффективно вычисляемые действительные функции в модели вообще не вычислимы на практике.
Каве
@Kaveh Меня беспокоит неточность всего обсуждения, в вопросе и в ответах. Говорим ли мы о традиционных неисчислимых реалах или о вычислимых реалах? Из вашего последнего комментария вы говорите о «реальных функциях, которые мы считаем эффективными вычислимыми на практике», поэтому я склонен полагать, что речь идет о вычислимых действительных значениях. Что вы на самом деле имеете в виду?
Бабу
8

Модель, которую вы описываете, известна как модель Блюма-Шуб-Смейла (BSS) (также модель Real RAM) и действительно используется для определения классов сложности.

Некоторые интересные проблемы в этой области являются классы , N P R , и, конечно , вопрос о том , P R = N P R . Под P R мы понимаем, что задача полиномиально разрешима, N P R - это проблема полиномиально проверяемой. Есть твердость / Полнота вопросы о классе N P R . Примером полной задачи N P R является задача Q P S , Квадратичная полиномиальная система, где входными данными являются вещественные полиномы впрNпрпрNпрпрNпрNпрNпрQпS переменные и р 1 , . , , , Р пR [ х 1 , . , , , x n ] степени не более 2, и каждый многочлен имеет не более 3 переменных. Вопростомсуществует общее действительное решение R п , такоечто р 1 ( ) , р 2 ( ) , . , , p n ( a ) = 0мп1,,,,,пN р[Икс1,,,,,ИксN]рNп1(a),п2(a),,,,пN(a)знак равно0, Это полная проблема Nпр

Но что более интересно, была некоторая работа над отношениями между , (Probalistically Checkable Proofs), над Реалами, то есть классом P C P R , и как это связано с алгебраическими моделями вычислений. Модель BSS показывает все N P за реалами. Это стандарт в литературе, и сегодня мы знаем, что у N P R есть «прозрачные длинные доказательства» и «прозрачные короткие доказательства». Под "прозрачными длинными доказательствами" подразумевается следующее: N P R содержится в P C P R ( p o l yпСппСпрNпNпрNPR . Существует также расширение, в котором говорится, что «Почти (приблизительная) короткая версия» также верна. Можем ли мы стабилизировать доказательство и обнаружить ошибки, проверяя значительно меньше (реальных) компонентов, чем n ? Это приводит к возникновению вопросов о существовании нулей (системы) одномерных многочленов, заданных прямой программой. Кроме того, под «прозрачными длинными доказательствами» мы подразумеваемPCPR(poly,O(1))n

  1. «прозрачный» - только для чтения,O(1)

  2. long - суперполиномиальное число вещественных компонент.

Доказательство привязано к , и, конечно же, один из способов взглянуть на реальные задачи - это то, как они могут быть связаны с суммой подмножеств - даже алгоритмы аппроксимации для реальных задач были бы интересны - как для оптимизации - Линейное программирование, которое мы знаем находится в классе F P , но да, было бы интересно посмотреть, как аппроксимируемость может повлиять на полноту / твердость для случая задач N P R. Кроме того, другим вопросом будет N P R = c o - N P R ? 3SATFPNPRNPR = co-NPR

Размышляя о классе , существуют также классы подсчета, позволяющие рассуждать о полиномиальной арифметике. В то время как # Р является класс функций F , определенная над { 0 , 1 } N , для которого существует многочлен времени машина Тьюринга M и полином р со свойством п N , и х { 0 , 1 } n , f ( x )NPR#Pf{0,1} NMpnNx{0,1}nf(x)считает количество строк { 0 , 1 } p ( n ), которое машина Тьюринга M принимает { x , y } . Для истин мы расширим эту идею, есть добавочные машины BSS - машины BSS, которые делают только сложение и умножения (без делений, без вычитаний). С аддитивными машинами BSS (узлы в вычислениях допускают только сложение и умножение) модель для # P становится той, в которой счетчик находится над векторами, которые дополняет машины аддитивной BSS. Итак, класс подсчета: # P a d dy{0,1}p(n)M{x,y}#P#Padd этот класс полезен при изучении чисел Бетти, а также характеристики Эйлера.

user3483902
источник
Реальная RAM (машина с произвольным доступом) или BSS (Blum-Shub-Smale) - это модель, упомянутая ранее, широко принятая в качестве нормы для рассуждений об этих классах.
user3483902
Нет, это утверждение абсолютно ложно. Например, взгляните на CCA-Net и посмотрите, сколько исследователей используют эту модель.
Каве
Итак, модели, используемые для классов сложности в посте, используют модель BSS, и со временем могут появиться другие модели, работают ли эти другие модели с классами сложности в посте? Кстати, комментарий был разъяснением моделей, используемых в рассматриваемых классах, к которым был адресован пост, поэтому не было никакого разъяснения относительно того, существуют ли другие модели. Опять же, разъяснение касалось моделей, используемых в классах, претензий не было.
user3483902