Показывая, что проблема в x не является x-полным

Question

А Экзистенциальная теория реальных в Pspace, но я не знаю, есть ли это Pspace-Complete. Анкет Если я считаю, что это не так, как я мог бы это доказать?

В целом, учитывая проблему в некотором классе сложности Икс, как я могу показать, что это нет X-Complete? Например, Икс может быть Нп, Pspace, Exptime.

Answer 1

На самом деле доказать $ x $ не является $ pspace $ -complete (под, скажем, снижение полинома), было бы чрезвычайно трудно сделать.

Если $ p = pspace $, то все нетривиальные (т.е., а не $ varnothing $, а не $ sigma^{ star} $) и бесконечные проблемы в $ pspace $ $ pspace $ -complete при сокращении полиномиального времени Анкет Поскольку экзистенциальная теория реальных обладает этой нетривиальной и бесконечной собственностью, доказывая, что она не $ Pspace $ -coplete подразумевает $ p neq pspace $. (Видеть Ответ на этот вопрос на cstheory.se для наброска доказательства.)

Answer 2

Проблема в $ x $ не является $ x $ -complete, если есть другие проблемы в $ x $, которые не могут быть уменьшены до этого. Одним из простых (но, возможно, только для тривиальных примеров) метод того, что ваша проблема также является в каком -то другом классе сложности $ y $, так что $ y submet x $.

Например, если вы хотите показать, что ваша проблема не завершена $ exptime $, то достаточно показать, что она находится в $ p $, поскольку $ P submetNeq Exptime $. Однако, если вы хотите показать, что проблема не является $ np $ -complete, то не обязательно достаточно, чтобы показать, что она находится в $ p $, поскольку неизвестно, является ли $ p = np $.

Answer 3

Посмотрите на принятый ответ на этот вопрос о Mathoverflow, Какие методы существуют, чтобы показать, что проблема не является NP-полной?. Анкет Он отвечает на случай, когда x = np.

Answer 4

Как писал Райан, доказать, что проблема не сложно, нелегко.

Пусть $ Q $ станет проблемой в классе сложности $ x $, а $ s $ закрыта $ leq $ снижение. Доказательство, что $ Q $ не является $ x $ -Hard wrt $ leq $, эквивалентно разделению класса сложности, полученным путем закрытия $ q $ wrt $ leq $. Теперь, если $ Q $ сложно для другого класса $ y $ wrt $ leq $, то это означает отделение $ y $ от $ x $. Как вы знаете, не так много результатов разделения.

В вашем случае $ x = mathsf {pspace} $, $ leq = leq^ mathsf {p} _m $ и $ y = mathsf {p} $.

Поскольку мы не можем доказать такие результаты в данный момент (за возможным исключением Райана :), вместо того, чтобы доказать, что $ Q $ не является $ x $-Hard, мы показываем, что это в классе сложности, который есть поверил быть меньше, чем $ x $. Например, если вы показываете, что $ mathrm {th} _ exists ( mathbb {r,+, times, 0,1}) $ находится в $ mathsf {ph} $, тогда это будет принято как убедительные доказательства того, что $ Q $ не будучи $ x $-Hard. (На языке логиков, если вы не можете доказать безоговорочный результат, попробуйте доказать условное, предполагая, что трудно доказать, но широко распространено заявление, как $ mathsf {p} neq mathsf {pspace} $).