Как судить о том, что определение вычислительной сложности вещественных чисел является естественным или подходящим?

11

Как мы знаем, определение вычислительной сложности алгоритма практически не вызывает противоречий, но определение вычислительной сложности вещественных чисел или моделей вычислений над действительными значениями не в таком случае. Мы знаем модель и модель Блюма и Смалеса в книге «Вычислительный анализ». И, похоже, модель в Computable Analysis соответствует классической модели, но определение вычислительной сложности вещественных чисел не может быть перенесено в классическую модель.

Как судить о том, что определение вычислительной сложности вещественных чисел является естественным или подходящим?

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

XL _At_Here_There
источник
Для вашего первого вопроса «естественный» является очень субъективным понятием, и в зависимости от человека, которого вы спрашиваете, одно или другое определение будет считаться наиболее естественным. Что касается «подходящего», то это зависит: модель BSS кажется подходящей для вычислительной геометрии или вычислительной алгебраической геометрии, а модель в Computable Analysis больше подходит для ... вычислимого анализа! Я не понимаю второй вопрос.
Бруно
@ Bruno, спасибо за ваш комментарий, я думаю, что модель в вычислимом анализе, и не знаю, как применить определение вычислительной сложности к вычислению действительного числа над классической моделью, такой как машина Тьюринга, так как вычислительная сложность действительного числа над моделью в вычислимом анализе зависит от его представления, а именно от ввода для его вычисления.
XL _At_Here_There
3
Вы, кажется, думаете, что есть понятие сложности для вычисления действительного числа, которое не зависит от представления действительных чисел. Что заставляет вас думать так? Это не относится и к классической сложности. Имеет значение, имеете ли вы ленту или машину с ОЗУ, важно, представляете ли вы графики с помощью списков смежности или 01-матриц и т. Д.
Андрей Бауэр,
3
Но это не правда, что сложность не зависит от представления. Переключаясь на глупое представление, вы всегда можете разрушить сложность алгоритма. Вопрос, который нужно задать: «Что такое хорошее представление о входных данных?» Для дискретных задач это гораздо легче ответить, чем для реальных чисел, потому что каждый хорошо понимает, что значит «не тратить биты».
Андрей Бауэр
3
модель BSS кажется подходящей для вычислительной геометрии - см. мой ответ на связанный вопрос . Модель Real RAM, используемая вычислительными геометрами, предшествует Blum, Shub и Smale почти на десять лет.
Джефф

Ответы:

13

Я не совсем уверен, что вопрос здесь, но я могу попытаться сказать немного, чтобы устранить возможные недоразумения.

Прежде всего, если мы говорим о сложности отображения , нет смысла спрашивать: «Что такое хорошее представление для f:RR ? «Вместо этого вы должны спросить« Что такое хорошее представление длявсехвходных данныхf? ». Сравните ситуацию с более простой в дискретной математике: когда вы обсуждаете алгоритм, который принимает граф в качестве входных данных, вы не спросите «Должны ли мы представлять граф Петерсена в виде списка смежности или в виде двоичной матрицы?», но вместо этого вы автоматически думаете оединомпредставлении, которое будет работать для всех графов.2f

Еще одно предупреждение. Изменяя представление входных данных, мы всегда можем сделать любую задачу (включая невычислимую) тривиально вычисляемой: чтобы сделать вычислимой, представим элементы A в виде пар ( a , f ( a ) ) . Тогда вы можете «вычислить» f по второй проекции. Это показывает, что нам нужны четкие критерии того, что значит представлять данные.f:ABA(a,f(a))f

Я написал несколько раз о том, что он принимает , чтобы представлять элементы . Ответ зависит от того, что структура из R вы пытаетесь захватить. Если вы пытаетесь не захватывать структуру, вы можете, например, представить все реалы пустым списком. Разумный список условий для представления R состоит в том, что оно должно быть таким, чтобы:RRR

  1. Арифметические операции , × , - , / вычислимы, а также абсолютное значение | - | ,+×/||
  2. Существует программа, которая принимает (представление) вещественного и k N и выводит целые числа p , q, такие что | x - p / q | 2 - k , т. Е. Можно вычислить сколь угодно хорошие рациональные приближения.xkNp,q|xp/q|2k
  3. Существует программа, которая принимает (представления) вещественных значений и y и завершается тогда и только тогда, когда x < y , т. Е. Строгий порядок является полуразрешимым.xyx<y
  4. Дана последовательность (представлений) такая, что | х н + 1 - х н | 2 - n представление для предела lim n x n может быть вычислено.(xn)n|xn+1xn|2nlimnxn

Существуют старые теоремы (см. Введение к этой статье для ссылок), которые объясняют, почему эти условия являются правильными. Эти теоремы также показывают, что любые два таких представления вещественных чисел вычислимо изоморфны, то есть мы можем переводить между ними с помощью программ. Это устанавливает некоторые критерии правильности, которые выбрасывают ошибочные идеи.

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

Другим примером, который исключают вышеуказанные условия, является модель Блюма-Шуб-Смейла, потому что в ней вы не можете вычислить пределы последовательностей. Лучше сказать, что модель BSS работает на дискретном упорядоченном подполе реалов (генерируемых какими-либо параметрами), а не на самих реалах.

Среди правильных представлений вещественных чисел некоторые более эффективны, чем другие, хотя это довольно трудная тема для обсуждения, поскольку действительные числа являются бесконечными объектами. Матиас Шредер отметил, что для разумной теории сложности следует обратить внимание на топологические свойства представления.

f:RRRxR

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

Андрей Бауэр
источник
2
Большое спасибо за ваш ответ и так много ссылок. Я чувствую себя неловко из-за некоторых понятий сложности вычислений, позвольте мне прочитать справочник и немного подумать, и привести пример, если я могу найти подходящий, чтобы объяснить, почему мне так неудобно (это звучит забавно, но мой опыт подсказывает мне если я чувствую себя неловко, должно быть что-то особенное)
XL _At_Here_There
4
По моему опыту, чувствовать себя некомфортно из-за новых знаний - это хороший знак, и обычно это является предпосылкой для просветления.
Андрас Саламон
3

<kO(t)O(t)O(t)O(t2log(t)log(log(t))), Как указывалось, топологические соображения полезны, никто не знает, существует ли какой-либо топологический контекст, разработанный для этой модели вычислений, который допускает реальные вычисления, которые имеют неопределенность в точности.

user3483902
источник
Не могли бы вы дать некоторую ссылку на возможную модель оперативной памяти?
XL _At_Here_There
См. Выше в разделе «... эта ссылка заявляет ...» есть ссылка на статью.
user3483902
2
Спасибо за указание на работу Brattka & Hertling, я собирался упомянуть об этом и забыл. Я просто хотел бы отметить, что модель Feasible RAM не включает в себя функции высшего порядка, в частности, она не может вычислить предел (быстрой) последовательности Коши, поэтому я бы не посчитал ее точной реализацией "вещественных чисел". Он может вычислить, так сказать, один предел «на верхнем уровне» (см. Часть статьи, в которой говорится о рациональных приближениях функций).
Андрей Бауэр