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

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

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

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

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

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

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

complexity-theory reference-request computation-models history Майк Батталья
источник

У Ювала Фильмуса есть небольшая заметка, в которой кратко изложено, как решить любую проблему в NP (и я думаю, что любую проблему в PSPACE?) За полиномиальное время, используя оперативные ОЗУ. Возможно, он опубликует ссылку на это, и вы можете просмотреть методы, чтобы посмотреть, можно ли их обобщить, чтобы исключить необходимость деления.

\sum_{i = 0}^{2^{n} - 1} 2^{c i}

$\sum_{i=0}^{2^n-1} 2^{ci}$

c

$c$

n, c

$n,c$

(2^{c 2^{n}} - 1) / (2^{c} - 1)

$(2^{c 2^n}-1)/(2^c-1)$

n

$n$

c

$c$ если мы допустим разделение, но можно ли это сделать без разделения? Если это возможно, я подозреваю, что аналогичные результаты будут применимы и к вашей модели.

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

Майк Батталья

@DW Моя заметка показывает, как решить все проблемы в PSPACE за полиномиальное время. К сожалению, вам нужно использовать побитовые операторы (побитовые AND и OR; оба они эквивалентны). В то время я кратко думал о том самом вопросе, который вы задаете, но не пришел ни к какому выводу. Вы можете найти все это здесь , хотя кажется, что вы уже знаете об этом.

Ювал

P \in PSPACE

$\text{P} \in \text{PSPACE}$

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

Ответы: