Importance: High ✭✭✭
Author(s): Folklore
Recomm. for undergrads: no
Prize: €100, from me (Cenny Wenner)
Posted by: cwenner
on: April 4th, 2009

\begin{problem} Is there a problem that can be computed by a Turing machine in polynomial space and unbounded time but not in polynomial time? More formally, does P = PSPACE? \end{problem}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

If $P \neq NP$, then $P \neq NP, NP^{NP}, \dotsc, PH, P^{\#P}, PSPACE = NPSPACE$, and a whole bunch more separations can be shown. In the light of this, if one believes that $P \neq NP$, then it is \textit{naive} to try to directly separate P from NP. In the words of the great George Polya, "\textit{If there is a problem you can’t solve, then there is an easier problem you can solve: find it.}" The P versus PSPACE question is one of the easiest such questions and would constitute an astonishing discovery in its own right. In particular, it would be the first separation result of this kind.

\section{Problem Approaches} How do we approach this problem? I don't know, readers please contribute. My personal take would be circuit complexity, i.e. functions that are known not to be computable with circuits of polynomial size. Another would be descriptive complexity: show that there is a property that can be expressed in second-order logic with a transitive closure operation which cannot be recognized in polynomial time.[N87] Fenner offered an interesting characterization of the P versus PSPACE question in terms of reductions.[FKR89] P versus PSPACE was also as an intermediate step towards the P versus NP prize by the Clay institute.[F05]


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

[F05] Harvey M. Friedman: Clay Millenium Problem: P = NP, manuscript, 2005. \href[[pdf]]{http://www.math.ohio-state.edu/~friedman/pdf/P=NP10290512pt.pdf}

[FKR89] Fenner,, S. A. and Kurtz,, S. A. and Royer,, J. A.: Every polynomial-time 1-degree collapses iff P=PSPACE, SFCS '89: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, 1988, pp. 624-629, \href[citeseer]{http://citeseerx.ist.psu.edu/viewdoc/summary?doi=} \href[acm]{http://dx.doi.org/10.1109/SFCS.1989.63545} \href[[pdf]]{http://citeseerx.ist.psu.edu/viewdoc/download?doi=}

[N87] Neil Immerman: Languages that Capture Complexity Classes, SIAM Journal of Computation 16:4, 1987. \href[citeseer]{http://citeseerx.ist.psu.edu/viewdoc/summary?doi=} \href[[pdf]]{http://citeseerx.ist.psu.edu/viewdoc/download?doi=}

* indicates original appearance(s) of problem.