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 . Did we make any progress/anti-progress towards resolving the 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 is defined as follows :

: Given an table filled with entries from , which we interpret as the multiplication table of an -element groupoid, and a subset of which includes element 1, determine whether the subgroupoid , defined as the closure of under the groupoid product, includes element .

**Barrington-McKenzie Conjecture :** For each , a branching program in which each node can only evaluate a binary product within an -element groupoid, branching ways according to the possible outcomes, must have at least nodes to solve all instances with singleton starting set .

The problem is known to be P-complete [JL’76]. Barrington-McKenzie Conjecture would imply that for any . In particular, it would imply that . 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 . 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 -ary tree of height , whose internal nodes are labeled with -ary functions on , and whose leaves are labeled with elements of . Each node obtains a value in equal to its -ary function applied to the values of its children. The output is the value of the root.

In their paper they show that

and conjecture that

. 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

. 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)*

### Like this:

Like Loading...