NP intersect coNP

NP is the set of languages that have short proofs. coNP is the set of languages that have short refutations. Note that coNP is not the complement of NP. NP \cap coNP is non-empty. It is easy to see that all languages in P are in NP \cap coNP i.e., P \subseteq NP \cap coNP. It is conjectured that P \subsetneq NP \cap coNP. i.e., there are problems in NP \cap coNP that are not in P. Following are some problems in NP \cap coNP that are not known to be in P.

Factoring : Given an integer what is the complexity of finding its factors. Every integer always has a unique factorization. Hence, Factoring is very different from the NP-complete problems. The following exercise states that it is highly unlikely that Factoring is NP-complete. On the other hand if Factoring is in P then the world as we know today will be in chaos !! Factoring is conjectured to be an intermediate problem.

Exercise : If Factoring is NP-complete then NP = coNP.

The first step to solve the above exercise is to show that Factoring is in NP \cap coNP. In fact it is also in UP \cap coUP. Perhaps this is the strongest evidence that P \subsetneq NP \cap coNP.

Parity Games : Deciding which of the two players has a winning strategy in parity games is in NP \cap coNP, as well as in UP \cap coUP.

Stochastic Games : The problem of deciding which player has the greatest chance of winning a stochastic game is in NP \cap coNP [Condon'92]

Lattice Problems : The problems of approximating the shortest and closest vector in a lattice to within a factor of \sqrt{n} is in NP \cap coNP [AR'05].

All the above problems are not known to be in P.

Open Problems :

  • Are there other problems in NP \cap coNP that are not known to be in P.
  • PPAD, PLS have been defined to understand problems whose structure is different from NP-complete problems. Can we define new complexity classes to study the complexity of the above mentioned problems (and related problems if any) ?
  • Graph Isomorphism (GI) is also conjectured to be an intermediate problem. It is known that GI is not NP-complete unless Polynomial Hierarchy collapses to its second level. Can we improve this result by showing that GI is in coNP ? Whether GI is in coNP is an interesting open problem for a very different reason also. More on this in a future post.

References :

  • [Condon'92] Anne Condon: The Complexity of Stochastic Games Inf. Comput. 96(2): 203-224 (1992)
  • [AR'05] Dorit Aharonov, Oded Regev: Lattice problems in NP \cap coNP. J. ACM 52(5): 749-765 (2005)

Logspace vs Polynomial time

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)

Approximating TreeWidth

Today’s post is about TreeWidth. When I first came across treewidth, I became an instant fan.

Definition : A tree-decomposition of a graph G(V,E) is a pair (\{X_i | i \in I \}, T=(I,F)) where \{X_i | i \in I \} is a family of subsets of V, one for each node of T, and T is a tree such that :

  • The union of the sets X_i is equal to V.
  • for all edges (v,w) \in E, there exists an i \in I with v \in X_i and w \in X_i.
  • for all i,j,k \in I : if j is on the path from i to k in T, then X_i \cap X_k \subseteq X_j.

The treewidth of a tree-decomposition is max_{i \in I}|X_i| - 1. The treewidth of a graph G is the minimum treewidth over all possible tree-decompositions of G.

Following are some interesting facts :

  • Exercise : TreeWidth of a tree is 1.
  • Exercise : TreeWidth of a clique on n vertices in n-1.
  • Determining whether treewidth of a given graph is at most k is NP-complete.
  • See [BGHK'95] for interesting applications of treewidth Eg : Choleski factorization on sparse symmetric matrices.
  • There is an analogous notion of pathwidth which is also NP-complete.

Approximating tree-width : Bodlaender et. al [BGHK'95] presented an O({\log}n) factor approximation algorithm for treewidth. This also gives an O({{\log}^2}n) factor approximation algorithm for pathwidth. Their algorithm works by repeatedly finding vertex separators and uses Leighton-Rao’s algorithm at its heart. The main insights from their paper are as follows :

  • If there is a factor \alpha approximation algorithm for vertex separator then there is an O(\alpha) approximation algorithm for treewidth.
  • if there is a factor \beta approximation algorithm for treewidth then there is an O(\beta{\log}n) approximation algorithm for pathwidth.

In 1995 the best known approximation factor for vertex separator was O({\log}n). Feige, Hajiaghayi and Lee [FHL'2008] improved this to O(\sqrt{{\log}n}). Hence we have O(\sqrt{{\log}n}) and O(\sqrt{{\log}n}{\cdot}{\log}n) factor approximation factors for treewidth and pathwidth respectively.

 

Special cases : What about computing treewidth of restricted classes of graphs ?

  • When k is any fixed constant, the graphs with treewidth k can be recognized, and a width k tree decomposition can be constructed for them, in linear time [Bodlaender'96].
  • Seymour and Thomas [ST'] showed that branchwidth of planar graphs can be computed in polynomial time. This implies a factor 3/2 approximation for treewdith of planar graphs.

Bounded TreeWidth : If the treewidth of a graph G is bounded by some fixed constant k, then several problems (that are NP-hard (even PSPACE-hard) for general graphs) can be solved in polynomial-time and often linear time !! Some of them include Maximum Independent set (hence maximum Clique), Hamiltonian cycle, Graph Isomorphism. Instead of listing all these problems, lets look at the following awesome theorem.

Courcelle’s Theorem : Any property of graphs definable in monadic second-order logic (MSO2) can be decided in linear time on any class of graphs of bounded tree-width. In other words, MSO2 is fixed-parameter tractable on any such class of graphs.

More information about Courcelle’s theorem can be found in this book. A recent paper (appeared today on arXiv) proved the following lower bound.
Theorem [KT'2010] : If C is any class of graphs which is closed under taking sub-graphs and whose tree-width is not bounded by a poly-logarithmic function then MSO2-model checking is intractable on C (under suitable assumptions from complexity theory)
There are several open problems related to treewidth, pathwidth, branchwidth and the related cops-robber games. Following are some that interest me :

Open Problems :

  • Perhaps the most interesting open question is to obtain a constant factor approximation for treewidth.
  • Bodlaender et. al ruled out absolute approximation algorithm, (unless P = NP) for treewidth and pathwidth. This is the best known hardness. Can we even rule out PTAS for treewidth ? Note that the hardness of treewidth implies the hardness of vertex separator (with constant factor blow-up).
  • How hard is computing treewidth of planar graphs ? NP-hardness is not known. Many researchers I talked to, believe that treewidth of planar graphs can be computed in polynomial-time.
  • Can the lower bound from [KT'2010] be improved ? In this context, it is interesting to note that Maximum Independent Set can be solved in polynomial time even when the treewidth is bounded by O({\log}n).
  • Datta et. al [DLNTW'2009] showed that planar graph isomorphism is in logspace. Is isomorphism for graphs with bounded treewidth in logspace ? I asked this question to some researchers, and this seems to be an open problem.

References :

    • [BGHK'95] Hans L. Bodlaender, John R. Gilbert, Hjálmtyr Hafsteinsson, Ton Kloks: Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree. J. Algorithms 18(2): 238-255 (1995)
    • [Bodlaender'96] Bodlaender, Hans L. : A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing 25 (6): 1305–1317 (1996)
    • [KT'2010] Stephan Kreutzer, Siamak Tazari Lower Bounds for the Complexity of Monadic Second-Order Logic arXiv:1001.5019

 

 

 

 

 

    • [FHL'2008] Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee: Improved Approximation Algorithms for Minimum Weight Vertex Separators. SIAM J. Comput. 38(2): 629-657 (2008)
    • [ST'90] PaulD.Seymour and Robin Thomas : Call Routing and the Ratcacher. Combinatorica 14(2): 217-241 (1994)
    • [DLNTW'2009] Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner: Planar Graph Isomorphism is in Log-Space. IEEE Conference on Computational Complexity 2009: 203-214

 

Open Problems from FOCS 2009

Here are some open problems (that interest me) from FOCS 2009. If you want to share an open problem, please leave a comment.

Starting with my paper…….

1) Reducibility Among Fractional Stability Problems [pdf]

Shiva Kintali, Laura Poplawski, Rajmohan Rajaraman, Ravi Sundaram and Shang-Hua Teng.

Summary : We resolve the computational complexity of a number of outstanding open problems with practical applications and introduce a simple PPAD-complete game (the preference game). Here is the list of problems we show to be PPAD-complete, along with the domains of practical significance:  1) Fractional Stable Paths Problem (FSPP) – Internet routing;  2) Core of Balanced Games – Economics and Game theory;  3) Scarf’s Lemma – Combinatorics;  4) Hypergraph Matching – Social Choice and Preference Systems;  5) Fractional Bounded Budget Connection Games (FBBC) – Social networks; and 6) Strong Fractional Kernel – Graph Theory.

Open Problems : The complexity of Discrete Ham Sandwich Problem and Necklace Splitting Problem are open. These are shown to be in PPAD by Papadimitiou in 1994.

2) Linear systems over composite moduli [pdf]

Arkadev Chattopadhyay and Avi Wigderson.

Summary and Open Problems : Dick Lipton already summarized their result along with open problems.

3) Regularity Lemmas and Combinatorial Algorithms [pdf]

Nikhil Bansal, Ryan Williams

Summary : This paper presents new combinatorial algorithms for Boolean matrix multiplication (BMM) and preprocessing a graph to answer independent set queries. The authors give the first asymptotic improvements on “combinatorial” algorithms for dense BMM in many years, improving on the Four Russians O(n^3/(log^{2}n)) bound. Their use of Triangle removal lemma and Regularity lemma are particularly interesting.

Open Problems : Ryan mentioned the following open problems in his talk : (1) Can one construct a Weak Regular partition in O(n^{2.9}) time, deterministically ? (2) Can their techniques be applied to All Pairs Shortest Paths Problems ? (3) is there a Regularity concept that is better suited for Matrix Multiplication ?

4) Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP [pdf]

Aaron Archer, MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Howard Karloff

Summary : They give a factor 1.990283 approximation algorithm for Prize-collecting TSP. This is the first result to break the barrier of 2 improving the primal-dual algorithm  of Goemans and Williamson. Recently Goemans, presented a 1.91457-approximation algorithm for the prize-collecting travelling salesman problem.

Open Problem : Obvious open problem is to improve this approximation factor.

5) Blackbox Polynomial Identity Testing for Depth 3 Circuits [pdf]

Neeraj Kayal and Shubhangi Saraf.

Open Problems : This paper has a well-written open problems section with specific open problems. If you are interested in polynomial identity testing, I encourage you to read them.

Complexity of Matrix Multiplication

Given an undirected graph G(V,E), how fast can we detect if G is triangle-free ? Cubic time is obvious. Let A be the adjacency matrix of G. We can detect triangle-freeness of G in the same complexity as multiplying two boolean matrices (AxA) (duh !!). This simple algorithm is the best known !! In other words, following is the open problem :
* Is testing triangle-freeness as difficult as the Boolean multiplication of two |V| x |V | matrices?
A recent paper [1] addressess this problem partially. In a related note, the complexity of all pairs shortest paths (APSP) is still unresolved. Is APSP (for undirected graphs) as difficult as the Boolean multiplication of two |V| x |V | matrices?
[1] N. Alon, T. Kaufman, M. Krivelevich, and D. Ron. Testing triangle-freeness in general graphs. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 279–-288, 2006.

Today’s post is about the following question and related problems.

Given an undirected graph G(V,E), how fast can we detect if G is triangle-free ?

Cubic time is obvious. A faster algorithm computes the square of the adjacency matrix of G and runs in time n^{\omega}, where \omega is the matrix multiplication exponent. This simple algorithm is the best known !!

Is testing triangle-freeness as hard as the Boolean multiplication of two |V| x |V | matrices?

Look at [AKKR'06] for recent results. A related problem is all pairs shortest paths (APSP). This is a fundamental graph problem and its exact complexity is still open.

Is APSP (for undirected graphs) as difficult as the Boolean multiplication of two |V| x |V | matrices?

These problems are tightly related to matrix multiplication, whose complexity is also open. The best value of \omega is 2.376. At Barriers Workshop, Chris Umans presented an exciting group-theoretic approach [CU'03, CKSU'05] to improving \omega. Using their techniques, the best value of \omega they achieved is 2.41. In their paper, they made two conjectures, one combinatorial and the other algebraic. Either one would imply that the exponent of matrix multiplication is 2.

Is \omega= 2 ?
Now, that would be a surprise in mathematics and theory. Many well-known problems are reducible to matrix multiplication. Eg : determinant, LUP decompositions, matrix inversion and many problems in linear algebra.

The techniques which led to 2.376 are primarily based on divide and conquer. The technique of [CU'03, CKSU'05] is a different one and worth pursuing. Are there any other techniques explored ? If you know of other techniques, please leave a comment, even if they resulted in a modest value of \omega.


References :

  • [AKKR'06] N. Alon, T. Kaufman, M. Krivelevich, and D. Ron. Testing triangle-freeness in general graphs. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 279–-288, 2006.
  • [CKSU'05] Henry Cohn, Robert D. Kleinberg, Balázs Szegedy, Christopher Umans. Group-theoretic Algorithms for Matrix Multiplication. FOCS 2005: 379-388
  • [CU'03] Henry Cohn, Christopher Umans: A Group-Theoretic Approach to Fast Matrix Multiplication. FOCS 2003: 438-449

Random Restriction and Circuit Lower Bounds

The class \aczero\ consists of all uniform families of circuits of constant depth and polynomial size, with unlimited-fanin AND and OR gates. NOT gates are allowed only at the inputs. The class \saczero\ is the semi-unbounded version of \aczero\ i.e., AND gates have constant fan-in.

The class AC^0 consists of all uniform families of circuits of constant depth and polynomial size, with unlimited-fanin AND and OR gates. NOT gates are allowed only at the inputs. The class SAC^0 is the semi-unbounded version of AC^0 i.e., AND gates have constant fan-in. In the class NC^0  both AND and OR gates have constant fan-in. The following strict hierarchy is known.

For all prime numbers p, NC^0 \subsetneq SAC^0 \subsetneq AC^0 \subsetneq AC^0[p] \subsetneq TC^0.

Todays post is is about the following theorem.

Theorem : SAC^0 \subsetneq AC^0

Proof : AC^0 is closed under complementation and SAC^0 is not.


Exercise : Prove that SAC^0 is not closed under complementation.

Recently I came up with an alternate proof of the above theorem using the technique of random restriction of Furst, Saxe and Sipser [FSS'81]. I think my proof can be given as a cool homework problem in introductory complexity theory course. Here it goes…..

Let G(V,E) be a directed simple graph (i.e., G does not have self-loops or multi-edges) with |V|=n and |E|=m. Let indegree(v) represent the indegree of a vertex v \in V. Motivated by cycle languages, we define the language Positive Indegree as follows :

Positive Indegree = \{ <G(V,E)>\ |\ indegree(v)\ \geq\ 1\ \forall\ v\ \in\ V\}.

G is represented as (x_1,y_1),\dots,(x_m,y_m) where each x_i and y_i is in \{1,2,\dots,n\} encoded as binary strings. The meaning of (x,y) is that there is a directed edge from x to y. We may assume that circuits computing Positive Indegree will have m = O(n^2) binary inputs in a prespecified order.

Exercise : Positive Indegree \in AC^0.

Lemma : If a CNF or a DNF computes Positive Indegree, then
  • each term includes at least n-1 variables, and
  • there are at least n terms.

Hence there is no SAC^0 circuit of depth two for Positive Indegree.

    Proof : We will prove this lemma for CNFs. The proof for DNFs is similar. Let \mathcal{C} be a CNF circuit computing Positive Indegree.
    • Assume that \mathcal{C} has some term t that depends on less than n-1 variables. Then when all inputs to t are 0, t outputs 0 and hence \mathcal{C} outputs 0. Consider the graph H consisting of a cycle on n-1 vertices (say v_1,\dots,v_{n-1}) and an isolated vertex v_n. Note that H \notin Positive Indegree. Let H_i be the graph obtained by adding the edge (v_i,v_n) to H. Now H_i \in Positive Indegree for 1 \leq i \leq n-1. If t does not depend on all variables of the form (v_i,v_n) then \mathcal{C} outputs 0 for some H_i, which is a contradiction.
    • Consider the graph F^i consisting of a cycle on n-1 vertices (these are the vertices from v_1,\dots,v_{n} except v_i) and an isolated vertex v_i. \mathcal{C} must output zero on F^i for 1 \leq i \leq n. \mathcal{C} outputs 0 only when one of the terms (OR gates) outputs zero. But each OR gate outputs 0 on exactly one assignment of the input variables, Hence, \mathcal{C} must have at least n terms.
    Restriction : Let \mathcal{C} be a circuit computing Positive Indegree. Setting an input of \mathcal{C} to 0 (resp. 1) corresponds to deleting (resp. contracting) the corresponding edge from the input graph G.

    Observation : If some of the inputs of \mathcal{C} are restricted to 0 or 1, the resulting circuit still computes Positive Indegree, albeit on a smaller graph.

    Theorem : Positive Indegree \notin SAC^0.
    Proof : We assume that there is an SAC^0 circuit (say \mathcal{C} of some constant depth d) computing Positive Indegree and derive a contradiction. Using the random restriction technique of [FSS'81] we squash \mathcal{C} down to depth d-1 while still computing Positive Indegree on many variables. This squashing still preserves the constant fanin of AND gates. We repeat this method d-2 times to obtain an SAC^0 circuit of depth 2 with constant AND fanin, which contradicts the previous lemma.

    Corollary : SAC^0 \subsetneq AC^0.

    References :
    • [FSS'81] Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. In FOCS, pages 260–270, 1981.

    Relativization Barrier

    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.

    Finding a Second Hamilton Circuit

    De
    Given an undirected graph does it have a Hamilton circuit ? It is well-known that this is an NP-complete problem. Consider the following problem :
    ANOTHER HAMILTON CIRCUIT : Given a Hamilton circuit in a graph find another hamilton circuit.
    It is easy to see that ANOTHER HAMILTON CIRCUIT is FNP-complete. What if we are given a Hamilton graph which is guaranteed to have a second Hamilton circuit. Following is a simple exercise :
    Exercise : Prove that if a cubic graph has a hamilton circuit then it must have a second one
    The above exercise is called Smith’s Theorem. Now consider the following computational poblem :
    SMITH : Given a Hamilton circuit in a 3-regular graph, find a second Hamilton circuit.
    Since the second hamilton circuit is guaranteed to exist, SMITH belongs to complexity class TFNP. Note that TFNP is a semantic class. In a beautiful paper [1] Papadimitriou defined several syntactic classes (e.g., PPA, PPAD, PPP) in TFNP. Papadimitriou proved that SMITH is in the complexity class PPA [1]. Here is an open problem mentioned in [1].
    Open Problem : Find a polynomial time algorithm for SMITH (or) Prove that SMITH is PPA-complete.
    [1] Christos H. Papadimitriou: On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. J. Comput. Syst. Sci. 48(3): 498-532 (1994)

    Deciding if an undirected graph has a Hamilton circuit is a well-known NP-complete problem. Let’s consider the following problem :

    ANOTHER HAMILTON CIRCUIT : Given a Hamilton circuit in a graph find another hamilton circuit.

    It is easy to see that ANOTHER HAMILTON CIRCUIT is FNP-complete. What if we are given a Hamilton graph which is guaranteed to have a second Hamilton circuit. Following is a simple exercise :

    Smith’s Theorem : Prove that if a cubic graph has a hamilton circuit then it must have a second one

    Now consider the following computational poblem :

    SMITH : Given a Hamilton circuit in a 3-regular graph, find a second Hamilton circuit.

    Thomason’s proof [Thomason'78] of Smith’s theorem yields an algorithm that given one Hamiltonian cycle in a cubic graph, computes another one. Since the second hamilton circuit is guaranteed to exist, SMITH belongs to complexity class TFNP. Note that TFNP is a semantic class. In a beautiful paper [Papadimitriou'94] Papadimitriou defined several syntactic classes (e.g., PPA, PPAD, PPP) in TFNP. Infact one can convert Thomason’s proof  into a PPA-membership proof of SMITH. Simply put, PPA is the undirected version of the complexity class PPAD. Krawczyk showed that [Krawczyk'99] the “PPA-graph” of SMITH can have exponentially long paths, thus proving that Thomason’s algorithm is exponential in the worst case.

    Open Problems

    • Find a polynomial time algorithm for SMITH (or) Prove that SMITH is PPA-complete.
    • Are there special cases of SMITH solvable in polynomial-time ?

    References :

    • [Krawczyk'99] Adam Krawczyk: The Complexity of Finding a Second Hmiltonian Cycle in Cubic Graphs. J. Comput. Syst. Sci. 58(3): 641-647 (1999)
    • [Papadimitriou'94] Christos H. Papadimitriou: On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. J. Comput. Syst. Sci. 48(3): 498-532 (1994)
    • [Thomason'78] A. G. Thomason, Hamiltonian cycles and uniquely edge colourable graphs, Ann. Discrete. Math. 3 (1978), 259-268.

    Impagliazzo’s Worlds

    I am back in Atlanta after attending Valiant’s birthday celebrations, STOC 2009 and Impagliazzo’s Worlds workshop. Another upcoming workshop at Center for Computational Intractability is “Barriers in Computational Complexity” workshop from August 25-29, 2009. Today’s post is a brief introduction to the five Impagliazzo’s Worlds [Impagliazzo'95].

    Algorithmica is the world in which P=NP or NP \subseteq BPP.

    Heuristica is the world where NP problems are intractable in the worst case but tractable on average.

    Pessiland is the world in which there are hard average-case problems, but no one-way functions. As the name suggests this is the worst possible world.

    Minicrypt is the world in which one-way functions exist, but public-key cryptography is impossible.

    Cryptomania is the world in which public-key cryptography is possible.

    Open Problems : An obvious open problem is which world do we live in ? Does Pessiland exist ?

    References :

    • [Impagliazzo'95] Russell Impagliazzo : A Personal View of Average-Case Complexity. Structure in Complexity Theory Conference 1995: 134-147 [ps]

    Pigeonhole Completeness

    The Complexity of searching for Pigeonholes…….

    Today’s post is about a complexity class named PPP, introduced by Papadimitriou [Papadimitriou'94]. PPP stands for Polynomial Pigeonhole Principle. It is defined to capture the complexity of problems (in TFNP), whose totality is proved using the pigeonhole principle. Following is the standard problem for PPP.

    Definition : (EQUAL OUTPUTS) : Given a Boolean circuit C with n inputs and n outputs, either find an input x such that C(x)=0^n or two inputs x \neq x' such that C(x)= C(x').

    Exercise : If C is a monotone circuit then EQUAL OUTPUTS is in FP.

    Let us look at an example. 0-1 KNAPSACK is a well-known NP-complete problem. Given a set S of n positive integers and an integer W, the goal is to find a subset A \subseteq S whose elements sum to W. For any set S of n positive integers, if the sum of elements of S is less than 2^n-1, there exist two subsets of S with the same sum. This gives rise to “TFNP version” of 0-1 KNAPSACK. It is called EQUAL SUMS.

    Definition : (EQUAL SUMS) : Given a set S of n positive integers, such that the sum of elements of S is less than 2^n-1, find two subsets of S with the same sum.

    Exercise : Prove that EQUAL SUMS \in PPP.

    EQUAL SUMS is not known to be in FP. Our understanding of PPP is very limited. We don’t have any natural complete problem for PPP yet. As the following exercise suggests, it is unlikely that PPP-complete problems are in FP.

    Exercise : If PPP = FP then one-way permutations do not exist.

    Open Problems : Is Equal Sums PPP-complete [Papadimitriou'94] ? Are there other natural problems in PPP, that are not obviously in FP ? It is known that PPAD \subseteq PPP [Papadimitriou'94]. Is there a “geometric” version of Equal Sums in PPAD ?

    References :

    • [Papadimitriou'94] Christos H. Papadimitriou: On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. J. Comput. Syst. Sci. 48(3): 498-532 (1994) [pdf]