Один студент недавно попросил меня проверить доказательство твердости NP для них. Они выполнили сокращение в соответствии с:
Я уменьшаю эту проблему которая, как известно, является NP-полной, к моей проблеме (с многократным уменьшением многократного числа), поэтому является NP-трудной.
Мой ответ был в основном:
Поскольку у есть экземпляры со значениями из , он тривиально не вычисляется по Тьюрингу, поэтому вы можете пропустить сокращение.
Хотя формально это правда, я не думаю, что этот подход является проницательным: мы, безусловно, хотели бы иметь возможность уловить «присущую сложность» реальной задачи решения (или оптимизации), игнорируя ограничения, с которыми мы сталкиваемся при работе с реальной числа; расследование этих вопросов еще на один день.
Конечно, это не всегда так просто, как сказать: «Дискретная версия Subset Sum является NP-полной, поэтому непрерывная версия также« NP-hard »также». В этом случае сокращение легко, но есть известные случаи упрощения непрерывной версии, например, линейное или целочисленное программирование.
Мне пришло в голову, что модель RAM естественно распространяется на реальные числа; пусть каждый регистр хранит действительное число и соответственно расширяет основные операции. Модель равномерной стоимости все еще имеет смысл - так же, как и в дискретном случае, в то время как логарифмическая - нет.
Итак, мой вопрос сводится к следующему: существуют ли устоявшиеся представления о сложности реальных задач? Как они относятся к «стандартным» дискретным классам?
Поиски в Google дают некоторые результаты, например, это , но я не могу сказать, что установлено и / или полезно, а что нет.
Ответы:
Да. Есть.
В другом ответе упоминается модель real-RAM / BSS. У модели есть некоторые проблемы, и AFAIK не так много исследований по этому поводу. Возможно, это не реалистичная модель вычислений .
Более активное понятие реальной вычислимости - это модель вычисления более высокого типа. Основная идея заключается в том, что вы определяете сложность для функций более высокого типа, а затем используете функции более высокого типа для представления действительных чисел.
Исследование сложности функций высшего типа восходит, по крайней мере, к [1]. Для недавней работы проверьте статьи Акитоши Кавамуры о сложности реальных операторов.
Классическим справочником по сложности вещественных функций является книга Кер-Ко Ко [2]. В шестой главе более поздней книги Клауса Вейрауха [3] также обсуждается сложность реальных вычислений (но она больше сфокусирована на вычислимости, чем на сложности).
[1] Стивен Кук и Брюс Капрон, "Характеристики основных выполнимых функционалов конечного типа", 1990.
[2] Кер-И Ко, "Вычислительная сложность вещественных функций", 1991.
[3] Клаус Вейраух «Вычислительный анализ», 2000.
источник
Модель, которую вы описываете, известна как модель Блюма-Шуб-Смейла (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 PS переменные и р 1 , . , , , Р п ⊆ R [ х 1 , . , , , x n ] степени не более 2, и каждый многочлен имеет не более 3 переменных. Вопростомсуществует общее действительное решение R п , такоечто р 1 ( ) , р 2 ( ) , . , , p n ( a ) = 0м п1, . , , , рN ⊆ R [ x1, . , , , хN] рN п1( а ) , р2( ) , . , , пN( а ) = 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
«прозрачный» - только для чтения,O(1)
long - суперполиномиальное число вещественных компонент.
Доказательство привязано к , и, конечно же, один из способов взглянуть на реальные задачи - это то, как они могут быть связаны с суммой подмножеств - даже алгоритмы аппроксимации для реальных задач были бы интересны - как для оптимизации - Линейное программирование, которое мы знаем находится в классе F P , но да, было бы интересно посмотреть, как аппроксимируемость может повлиять на полноту / твердость для случая задач N P R. Кроме того, другим вопросом будет N P R = c o - N P R ?3SAT FP NPR NPR = co-NPR
Размышляя о классе , существуют также классы подсчета, позволяющие рассуждать о полиномиальной арифметике. В то время как # Р является класс функций F , определенная над { 0 , 1 } ∞ → N , для которого существует многочлен времени машина Тьюринга M и полином р со свойством ∀ п ∈ N , и х ∈ { 0 , 1 } n , f ( x )NPR #P f {0,1}∞ → N M p ∀n ∈ N x ∈ {0,1}n f(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 этот класс полезен при изучении чисел Бетти, а также характеристики Эйлера.
источник