Машинка Блюм-Шуб-Смале

В теории вычислений машина Блюма-Шаба-Смейла , или машина BSS , представляет собой модель вычислений, представленную Ленорой Блюм , Майклом Шубом и Стивеном Смейлом , предназначенную для описания вычислений над действительными числами . ^{[ 1 ]} По сути, машина BSS — это машина произвольного доступа с регистрами, которые могут хранить произвольные действительные числа и которые могут вычислять рациональные функции над действительными числами за один временной шаг. Она тесно связана с моделью Real RAM .

Машины BSS более мощны, чем машины Тьюринга , поскольку последние по определению ограничены конечным набором символов. ^{[ 2 ]} Машина Тьюринга может представлять счетное множество (например, рациональные числа) строками символов, но это не распространяется на несчетные действительные числа.

Определение

Машина BSS M задается списком $I$ из $N+1$ инструкции (будут описаны ниже), проиндексированы $0,1,\dots ,N$ . Конфигурация M представляет собой кортеж $(k,r,w,x)$ , где $k$ — индекс инструкции, которая будет выполняться следующей, $r$ и $w$ являются регистрами, содержащими неотрицательные целые числа, и $x=(x_{0},x_{1},\ldots )$ представляет собой список действительных чисел, все из которых, кроме конечного числа, равны нулю. Список $x$ считается хранящим содержимое всех регистров M . Вычисления начинаются с настройки $(0,0,0,x)$ и заканчивается всякий раз, когда $k=N$ ; окончательное содержание $x$ Говорят, что это выход машины.

Инструкции M могут быть следующих типов:

Вычисление : замена $x_{0}:=g_{k}(x)$ выполняется, где $g_{k}$ – произвольная рациональная функция (частное двух полиномиальных функций с произвольными действительными коэффициентами); регистры $r$ и $w$ может быть изменено либо $r:=0$ или $r:=r+1$ и аналогично для $w$ . Следующая инструкция $k+1$ .
Ветвь( $l$ ) : если $x_{0}\geq 0$ тогда иди $l$ ; еще идти $k+1$ .
Копировать ( $x_{r},x_{w}$ ): содержимое регистра чтения $x_{r}$ копируется в «записанный» регистр $x_{w}$ ; следующая инструкция $k+1$ .

Теория

Блюм, Шуб и Смейл определили классы сложности P (полиномиальное время) и NP (недетерминированное полиномиальное время) в модели BSS. Здесь NP определяется путем добавления к проблеме экзистенциально-квантифицированного вклада. Они ставят задачу, которая является NP-полной для определенного таким образом класса NP: существование корней многочленов четвертой степени. Это аналог теоремы Кука-Левина для вещественных чисел.

См. также

Ссылки

^ Блюм, Ленор ; Шуб, Майк ; Смейл, Стив (1989). «К теории вычислений и сложности над действительными числами: NP-полнота, рекурсивные функции и универсальные машины» (PDF) . Бюллетень Американского математического общества . 21 (1): 1–46. дои : 10.1090/S0273-0979-1989-15750-9 . Збл 0681.03020 .
^ Мински, Марвин (1967). Вычисления: конечные и бесконечные машины . Нью-Джерси: Prentice-Hall, Inc.

Дальнейшее чтение

Блюм, Ленор ; Какер, Фелипе ; Шуб, Майк ; Смейл, Стив (1998). Сложность и реальные вычисления . Спрингер Нью-Йорк. дои : 10.1007/978-1-4612-0701-6 . ISBN 978-0-387-98281-6 . S2CID 12510680 . Проверено 23 марта 2022 г.
Бюргиссер, Питер (2000). Полнота и редукция в теории алгебраической сложности . Алгоритмы и вычисления в математике. Том. 7. Берлин: Шпрингер-Верлаг . ISBN 3-540-66752-0 , Збл 0948.68082 .
Гредель, Э. (2007). «Теория конечных моделей и сложность описания». Теория конечных моделей и ее приложения (PDF) . Спрингер-Верлаг. стр. 125–230. Збл 1133.03001 .

[1] Блюм, Ленор ; Шуб, Майк ; Смейл, Стив (1989). «К теории вычислений и сложности над действительными числами: NP-полнота, рекурсивные функции и универсальные машины» (PDF) . Бюллетень Американского математического общества . 21 (1): 1–46. дои : 10.1090/S0273-0979-1989-15750-9 . Збл 0681.03020 .

[2] Мински, Марвин (1967). Вычисления: конечные и бесконечные машины . Нью-Джерси: Prentice-Hall, Inc.

[ 1 ]

[ 2 ]