Машины с произвольным доступом только с добавлением, умножением, равенством

13

В литературе достаточно ясно, что ОЗУ с удельной стоимостью с примитивным умножением являются необоснованными, поскольку они

  1. не может быть смоделировано машинами Тьюринга за полиномиальное время
  2. может решить PSPACE-полные задачи за полиномиальное время

Тем не менее, все ссылки, которые я могу найти по этой теме (Simon 1974, Schonhage 1979), также включают логические операции, целочисленное деление и т. Д.

Существуют ли какие-либо результаты для «разумности» ОЗУ, которые имеют только сложение, умножение и равенство? Другими словами, которые не имеют логических операций, усеченного целочисленного деления, усеченного вычитания и т. Д.?

Казалось бы, такие ОЗУ все еще довольно «неразумны». Основной красный флаг заключается в том, что они позволяют генерировать экспоненциально большие целые числа за линейное время, и из-за эффекта умножения свертки это может стать особенно сложным. Однако на самом деле я не могу найти никаких результатов, показывающих, что это допускает какой-либо «необоснованный» результат (экспоненциальное ускорение машины Тьюринга, необоснованное отношение к PSPACE и т. Д.).

Есть ли у литературы какие-либо результаты по этой теме?

Майк Батталья
источник
У Ювала Фильмуса есть небольшая заметка, в которой кратко изложено, как решить любую проблему в NP (и я думаю, что любую проблему в PSPACE?) За полиномиальное время, используя оперативные ОЗУ. Возможно, он опубликует ссылку на это, и вы можете просмотреть методы, чтобы посмотреть, можно ли их обобщить, чтобы исключить необходимость деления.
DW
Σязнак равно02N-12сясN,с(2с2N-1)/(2с-1)Nсесли мы допустим разделение, но можно ли это сделать без разделения? Если это возможно, я подозреваю, что аналогичные результаты будут применимы и к вашей модели.
DW
Вы знаете, где эта записка? Я видел литературу о том, что ОЗУ с удельной стоимостью являются неоправданно мощными, когда разрешены логические операции, и усеченное деление (или сдвиг), когда логические операции и усечения превращают все это в огромное параллельное устройство. Но где-то должен быть какой-то результат, показывающий, что даже просто умножение на единицу стоимости «неразумно» без других вещей, потому что, как уже упоминалось, вы можете быстро вычислить числа с большим количеством цифр, чем содержится в наблюдаемой вселенной. Но я не могу найти доказательства этому.
Майк Батталья
3
@DW Моя заметка показывает, как решить все проблемы в PSPACE за полиномиальное время. К сожалению, вам нужно использовать побитовые операторы (побитовые AND и OR; оба они эквивалентны). В то время я кратко думал о том самом вопросе, который вы задаете, но не пришел ни к какому выводу. Вы можете найти все это здесь , хотя кажется, что вы уже знаете об этом.
Ювал
пPSPACE

Ответы:

2

На днях я читал статью о параллельных машинах произвольного доступа без битовых операций, которые очень походили на то, что вы описываете. Для этих моделей NC известен как не равный P. Смотрите здесь: https://epubs.siam.org/doi/10.1137/S0097539794282930

Документ также можно найти на сайте профессора Малмулей.

exfret
источник