表明x中的问题不是x complete

Question

这 真实的存在理论 在 pspace, ，但我不知道是 pspace-complete. 。如果我认为不是这样，我该怎么证明？

更普遍地，考虑到某个复杂性课程的问题 X, ，我该如何证明它是 不是 X完整？例如， X 可能 NP, pspace, exptime.

Answer 1

实际上，证明$ x $不是$ pspace $ -complete（例如，在多项式时间降低）将非常困难。

如果$ p = pspace $，则所有非平凡（即，不是$ varnothing $，而不是$ sigma^{ star} $）和$ pspace中的无限问题是$ pspace $ - $ pspace $ - complete $ complete $ complete polynomial-imial time减少。由于真实的存在理论具有这种非平凡和无限的财产，因此证明了它 不是 $ pspace $ - complete将暗示$ p neq pspace $。 （看 在cstheory.se上解决这个问题的答案 用于证明的草图。）

Answer 2

$ x $中的问题不是$ x $ -complete，如果$ x $中的其他问题无法减少。一种直接的（但可能仅在琐碎的示例中有效）的方法是证明您的问题也是在其他一些复杂性类别$ y $中，因此$ y y subset x $。

例如，如果您想证明您的问题不是$ exptime $完成，则足以证明它在$ p $中，因为$ p subsetneq exptime $。但是，如果您想证明一个问题不是$ NP $ - complete，那么不一定足以证明它在$ p $中，因为不知道$ p = np $。

Answer 3

在Mathoverflow上查看此问题的接受答案， 存在哪些技术来表明问题不是NP完成的？. 。当x = np时，它回答了情况。

Answer 4

正如瑞安（Ryan）所写，证明问题并不容易。

让$ q $是复杂性$ x $的问题，$ s $是关闭的WRT $ leq $降低。证明$ q $不是$ x $ -hard wrt $ leq $相当于通过关闭$ q $ wrt $ leq $而获得的复杂性类别。现在，如果$ q $对于另一类$ y $ wrt $ leq $很难，则意味着将$ y $与$ x $分开。如您所知，分离结果不多。

就您而言，$ x = mathsf {pspace} $，$ leq = leq^ mathsf {p} _m $，$ y = yathsf {p} $。

因为我们目前无法证明此类结果（可能是Ryan除外：）代替证明$ Q $不是$ x $ - hard，我们证明它是一个复杂性的类别 相信 小于$ x $。例如，如果您显示$ mathrm {th} _ 已存在（ mathbb {r，+， times，0,1}）$ in $ mathsf {ph} $，则将其作为一个$ q $不是$ x $ - hard的有力证据。 （用逻辑学家的语言，如果您无法证明无条件的结果，请尝试证明有条件的结果，假设很难证明，但像$ Mathsf {p} neq neq Mathsf {pspace} $一样广泛相信语句）。