Показано, что проблема в X не X-Complete

Теория Экзистенциальная из реалов в PSPACE , но я не знаю , является ли это PSPACE-Complete . Если я считаю, что это не так, как я могу доказать это?

В более общем смысле, учитывая проблему в некотором классе сложности X , как я могу показать, что это не X-Complete ? Например, X может быть NP , PSPACE , EXPTIME .

На самом деле, доказать, что $X$ не является $PSPACE$ -полным (скажем, при сокращениях за полиномиальное время), было бы крайне сложно.

Если $P=PSPACE$ , то все нетривиальные (т. Е. Не и не ) и бесконечные задачи в являются -полными при сокращениях за полиномиальное время. Поскольку экзистенциальная теория вещественных чисел обладает этим нетривиальным и бесконечным свойством, доказательство того, что оно не является неполным, подразумевает . (См. Ответ на этот вопрос на CSTheory.SE для наброска доказательства.)Σ ⋆ P S P A C E P S P A C E P S P A C E P ≠ P S P A C $\varnothing$$\Sigma^{\star}$$PSPACE$$PSPACE$ $PSPACE$$P \neq PSPACE$

Проблема в не является X- полной, если есть другие проблемы в X, которые не могут быть сведены к ней. Один метод простой (но , возможно , лишь в силу тривиальных примеров) доказывали бы ваша проблема также в какой - то другой сложности класса Y такое , что Y ⊂ X .$X$$X$$X$$Y$$Y \subset X$

Например, если вы хотите , чтобы показать , что ваша проблема не полная, то достаточно , чтобы показать , что он находится в P , так как P ⊊ E X P T I M E . Однако, если вы хотите показать, что проблема не является N P -полной, тогда необязательно показывать, что она находится в P , поскольку неизвестно, является ли P = N P или нет .$EXPTIME$$P$$P \subsetneq EXPTIME$$NP$$P$$P = NP$

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

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

Пусть является проблема в классе сложности X и S замкнуто относительно ≤ сокращения. Доказательство того, что Q не является X- трудным по сравнению с ≤ , эквивалентно разделению класса сложности, полученного путем замыкания Q по сравнению с ≤ . Теперь, если Q трудно для другого класса Y WRT ≤ , то это означает , отделяя Y от X . Как вы знаете, результатов разделения не так много.$Q$$X$$S$$\leq$$Q$$X$$\leq$$Q$$\leq$$Q$$Y$$\leq$$Y$$X$

В вашем случае, , ≤ = ≤ Р м , а Y = Р .$X = \mathsf{PSpace}$$\leq = \leq^\mathsf{P}_m$$Y=\mathsf{P}$

Поскольку мы не можем доказать такие результаты в настоящее время (за исключением, возможно, Райана :), вместо доказательства того, что не является X- трудным, мы показываем, что он находится в классе сложности, который, как полагают, меньше, чем X , Например, если вы покажете, что T h ∃ ( R , + , × , 0 , 1 ) находится в P H , то это будет принято как убедительное доказательство того, что Q не является $Q$$X$$X$$\mathrm{Th}_\exists(\mathbb{R,+,\times,0,1})$$\mathsf{PH}$$Q$$X$-жесткий. (На языке логиков, если вы не можете доказать безусловный результат, попробуйте доказать условный результат, предполагая трудно доказать, но широко распространенное утверждение, такое как ).$\mathsf{P}\neq\mathsf{PSpace}$