P vs NP

One of the primary goals of complexity theory is separating complexity classes, a.k.a proving lower bounds. Embarrassingly we have only a handful of unconditional separation results. Separating P from NP is of course the mother of all such goals. Anybody who understands the philosophical underpinnings of the P vs NP problem would love to LIVE to see its resolution. Towards resolving this, we made some (“anti”)-progress (Eg : Relativization, Natural proofs, Algebrization) and have a new geometric complexity theory approach which relies on an Extended-Extended-Extended-Extended-Riemann-Hypothesis !! For more information about the history and status of P vs NP problem read Sipser’s paper [Sipser’92], Allender’s status report [Allender’09] or Fortnow’s article [Fortnow’09].

Today’s post is about the Logspace (L) vs Polynomial time (P) problem, which (in my opinion) is right next to the P vs NP problem in its theoretical importance. I guess many researchers believe that $L \neq P$ . Did we make any progress/anti-progress towards resolving the $L \neq P$ conjecture ? Here are two attempts both based on branching programs and appeared in MFCS with a gap of 20 years !!

1) A conjecture by Barrington and McKenzie (BM’89): The problem $GEN$ is defined as follows :

$GEN$ : Given an $n \times n$ table filled with entries from $\{1,2,\dots,n\}$ , which we interpret as the multiplication table of an $n$ -element groupoid, and a subset $S$ of $\{1,2,\dots,n\}$ which includes element 1, determine whether the subgroupoid $<S>$ , defined as the closure of $S$ under the groupoid product, includes element $n$ .

Barrington-McKenzie Conjecture : For each $n > 1$ , a branching program in which each node can only evaluate a binary product within an $n$ -element groupoid, branching $n$ ways according to the $n$ possible outcomes, must have at least $2^{n-2}$ nodes to solve all $n \times n$ $GEN$ instances with singleton starting set $S$ .

The problem $GEN$ is known to be P-complete [JL’76]. Barrington-McKenzie Conjecture would imply that $GEN \notin DSPACE({{\log}^k}n)$ for any $k$ . In particular, it would imply that $L \neq P$ . I don’t know if there is any partial progress towards resolving this conjecture.

2) Thrifty Hypothesis : This is a recent approach by Braverman et. al [BCMSW’09] towards proving a stronger theorem $L \neq LogDCFL$ . Stephen Cook presented this approach at Valiant’s 60th birthday celebration and Barriers Workshop. He also announced a $100 prize for solving an intermediate open problem mentioned in his slides.

Tree Evaluation Problem (TEP): The input to the problem is a rooted, balanced $d$ -ary tree of height $h$ , whose internal nodes are labeled with $d$ -ary functions on $[k] = \{1, . . . , k\}$ , and whose leaves are labeled with elements of $[k]$ . Each node obtains a value in $[k]$ equal to its $d$ -ary function applied to the values of its $d$ children. The output is the value of the root.

In their paper they show that $TEP \in LogDCFL$ and conjecture that $TEP \notin L$ . They introduce Thrifty Branching Programs and prove that TEP can be solved by a thrifty branching program. A proof of the following conjecture implies that $L \neq LogDCFL$ . For more details, read this paper.

Thrifty Hypothesis : Thrifty Branching Programs are optimal among deterministic branching programs solving TEP.

Open Problems :

My knowledge about the history of L vs P problem is limited. Are there other approaches/attempts in the last four decades to separate L from P ?

An intermediate open problem is mentioned in the last slide of these slides. The authors announced $100 prize for the first correct proof. Read their paper for more open problems.

References :

[BM’89] David A. Mix Barrington, Pierre McKenzie: Oracle Branching Programs and Logspace versus P. MFCS 1989: 370-379
[BCMSW’09] Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr: Branching Programs for Tree Evaluation. MFCS 2009: 175-186
[Sipser’92] Michael Sipser: The History and Status of the P versus NP Question STOC 1992: 603-618
[Allender’09] Eric Allender: A Status Report on the P Versus NP Question. Advances in Computers 77: 117-147 (2009) [pdf]
[Fortnow’09] Lance Fortnow: The status of the P versus NP problem. Commun. ACM 52(9): 78-86 (2009) [pdf]
[JL’76] Neil D. Jones, William T. Laaser: Complete Problems for Deterministic Polynomial Time. Theor. Comput. Sci. 3(1): 105-117 (1976)

I am back in Atlanta after attending an awesome Barriers Workshop. This workshop is mainly about the barriers in resolving P vs NP problem and possible techniques to overcome these barriers. It is a five day workshop covering circuits lower bounds, arithmetic circuits, proof complexity, learning theory and pseudo-random generators. I enjoyed every talk and panel discussions. Everybody seemed very positive that $P \neq NP$ .

Today’s post is a quick introduction to Relativization Barrier. I will write separate posts about natural proofs and algebrization barriers soon. Relativization Barrier is one of the first barriers we learn in an introductory graduate level complexity course.

In relativized world we grant the Turing machine M the access to an oracle that could compute some function A in a single time step. Such a machine, called oracle TM, computes relative to A, is represented by $M^A$ . Oracle TMs are used in Turing-reducibility, a generalization of mapping-reducibility.

The method of diagonalization relativizes i.e., any separation result in the real world, proved using diagonalization, extends to the relativized world. Baker, Gill and Solovay [BGS’75] showed that there exists oracles A and B for which $P^A$ and $NP^A$ are provably different and $P^B$ and $NP^B$ are provably equal. That is P vs NP has different answers in different worlds !! Hence techniques such as diagonalization, cannot be used to resolve P versus NP.

Theorem : An oracle A exists such that $P^A \neq NP^A$ . An oracle B exists such that $P^B = NP^B$ .

Let B be any PSPACE-complete problem. We have $NP^B \subseteq NPSPACE \subseteq PSPACE \subseteq P^B$ . The first and third containments are trivial and the second containment follows from Savitch’s theorem. Hence $P^B = NP^B$ . Constructing A is a non-trivial task. Look at Sipser’s book (page 350) for details of constructing A.

Therefore any solution to the P versus NP problem will require non-relativizing techniques i.e., techniques that exploit properties of computation that are specific to the real world i.e., techniques that analyze the computations not just simulate them.

References :

[BGS’75] T. Baker, J. Gill, and R. Solovay : Relativizations of the P=?NP question. SIAM J. Comput., 4:431–442, 1975.

Baker, Gill and Solovay [BGS’75] showed that techniques such as diagonalization,

cannot be used to resolve P versus NP. Such techniques would work in [relativized]

world, where both P and NP machines could compute some function

f in a single time step.

However, there are some relativized

worlds where P = NP, and other relativized worlds

where P != NP. Therefore any solution to the P versus NP

problem will require non-relativizing techniques i.e., techniques

that exploit properties of computation that are specific to

the real world.

My Brain is Open

Computational Complexity, Polyhedral Combinatorics, Algorithms and Graph Theory

Logspace vs Polynomial time

Relativization Barrier

Share this:

Share this: