Может ли любая NP-полная проблема быть решена с использованием не более чем полиномиального пространства (но при использовании экспоненциального времени?)

Я читал о NPC и его связи с PSPACE, и я хотел бы знать, могут ли проблемы NPC быть детерминированно решены с использованием алгоритма с наименьшим требованием к полиномиальному пространству, но потенциально с экспоненциальным временем (2 ^ P (n), где P - полиномиальный).

Более того, может ли оно быть обобщено до ОПЫТА в целом?

Причина, по которой я спрашиваю об этом, заключается в том, что я написал несколько программ для решения вырожденных случаев проблем с NPC, и они могут потреблять очень большие объемы оперативной памяти для сложных случаев, и мне интересно, есть ли лучший способ. Для справки см. Https://fc-solve.shlomifish.org/faq.html .

Вообще говоря, для любого алгоритма верно следующее:

1. Предположим, что - это алгоритм, который выполняется за время . Тогда не может занимать больше, чем места, так как для записи битов требуется время .$A$$f(n)$$A$$f(n)$$f(n)$$f(n)$
2. Предположим, что - это алгоритм, требующий пространства . Тогда за времени может посетить каждое из его различных состояний, поэтому ничего не может получить, выполнив более времени.$A$$f(n)$$2^{f(n)}$$A$$2^{f(n)}$

Это следует из того:

$\mathbf{NP}$ $\subseteq \mathbf{PSPACE}$

Утверждение известно как часть отношений между классами, как показано на следующей диаграмме:

Объяснение простое: проблема имеет сертификат полиномиальной длины . Алгоритм, который проверяет все возможные сертификаты, является алгоритмом, который решает во времени .$Q$ $\in$ $\mathbf{NP}$$y$$Q$$\large 2^{n^{O(1)}}$

Требуемое пространство:

• $y$ (многочлен от )$n$
• пространство, необходимое для проверки . Поскольку является полиномиальным сертификатом, его можно проверить за полиномиальное время, следовательно, он не может требовать больше, чем полиномиальное пространство.$y$$y$

Поскольку сумма двух полиномов также является полиномом, можно определить с помощью полиномиального пространства.$Q$

Пример:

Предположим, что является экземпляром 3-CNF для литералов с предложениями. Назначение - это некоторая функция .$\varphi$$x_1 \dots x_n$$m$$f$$f:\{x_1\dots x_n\} \rightarrow \{0,1\}$

Он гласит:

• Есть разных назначений.$2^n$
• Дано задание , требуется время , чтобы вычислить значение , поэтому он не может требовать больше , чем пространства.$f$$O(m)$$\varphi$$O(m)$

Таким образом, алгоритм который проверяет все возможные назначения, будет использовать полиномиальное пространство, работать в экспоненциальном времени и принимать решение 3-SAT.$A$

Это следует из того:

3-SAT , а так как 3-SAT является NP-Complete,$\in \mathbf{PSPACE}$$\mathbf{NP}$ $\subseteq \mathbf{PSPACE}$

Да. Вот набросок прямого доказательства.

$\mathrm{NP}$$M$$p$$M$$n$$p(n)$$p(n)$

$c$$M$$M$$c$$c^{p(n)}$$n$$c^{p(n)}$$p(n)$$c$$p(n)$$M$$i$$i$$i$$6$

$0\dots 0$$M$$c-1$$c^{p(n)}p(n)$$2p(n)$