A promise problem with an interesting upper bound

Shimon Even was one of the greats of theory, especially algorithms on graphs—his book Graph Algorithms is a classic. Unfortunately, he passed away in 2004 and will always be missed. His legacy includes many great results, many strong Ph.D. students, and among many other ideas the notion of a promise problem. He invented the latter in 1984 in joint work with Alan Selman and Yacov Yacobi. See the beautiful survey by Oded Goldreich on Even and the importance of promise problems.

Today I want to raise an interesting “promise problem” that is related to some earlier discussions we have had.

I knew Shimon, but never had the pleasure to write a paper with him. He had a wonderful way about him, he was full of energy, and was a joy to talk to on any topic.

I have a story about Even and me that happened when I was at Berkeley and he was visiting there—this was in 1979.

One fall day Shimon came into my office with a big smile on his face. I asked him to sit down, and he proceeded to explain what he found so amusing. The previous spring I had taught the undergraduate automata theory—at the level of Mike Sipser’s book—except that Mike was taking my class at the time. Not only did Mike take the class but a number of other graduate students did too. One I will call student X. He did okay in my class, and Shimon reminded me that I gave him a B. At Berkeley B was “passing” for a graduate student so I thought nothing much about giving him this grade.

Shimon smiled and told me:

You were the first teacher ever to give him a B. Ever. He had gotten A’s for every class he took since first grade.

I started to say something—but Shimon broke in and said that I had done a great thing. The student was so upset about the B that he was working extremely hard to get his research going. He even had considered leaving Berkeley to go to another department, but decided to stay. In a sense X wanted to prove me wrong.

Shimon thanked me. He said X was probably going to do terrific work and my giving him that single B may have been the spark he needed. I do not recall saying anything back to Shimon, but today X is a superstar. I would like to think that I helped in some small way. Perhaps I should give out more B’s.

Let’s turn to discuss a simple promise problem that I have been looking at recently.

The Promise Problem

I will call the problem ${\mathsf{TWOPATHS}}$. A function ${f(x)}$ is given that is computable in polynomial time on bit strings of length ${n}$. The function is 1-1 but can be “undefined” on some strings, and we also stipulate ${f(x) \neq x}$ for all ${x}$. Let’s use ${x \rightarrow y}$ to denote that ${f(x) = y}$. In a natural way the function defines a directed graph with ${\rightarrow}$ as the edge relationship. Every node has out-degree at most ${1}$ because ${f}$ is a function, and in-degree at most ${1}$ because ${f}$ is injective. It also has no self-loops because ${f(x) \neq x}$. Hence the graph is a disjoint union of paths and cycles.

We further stipulate that there are two special start nodes ${s_1,s_2}$ and two special end nodes ${t_1,t_2}$, which are given as part of the input. The promise is the resulting graph has exactly two paths, each starting from an ${s_i}$ and ending in an ${t_j}$.Thus, either

$\displaystyle \begin{array}{rcl} s_1 \rightarrow a_1 \rightarrow a_2 \rightarrow &\dots& \rightarrow a_k \rightarrow t_1 \\ s_2 \rightarrow b_1 \rightarrow b_2 \rightarrow &\dots& \rightarrow b_l \rightarrow t_2 \end{array}$

or

$\displaystyle \begin{array}{rcl} s_1 \rightarrow a_1 \rightarrow a_2 \rightarrow &\dots& \rightarrow a_k \rightarrow t_2 \\ s_2 \rightarrow b_1 \rightarrow b_2 \rightarrow &\dots& \rightarrow b_l \rightarrow t_1. \end{array}$

The task is to determine the end point of the paths: does the path from ${s_1}$ end in ${t_1}$ or ${t_2}$?

Notice that the property of ${t_1,t_2}$ being sinks is not part of the “promise.” It does not have to be because it is already decidable in polynomial time: being able to tell that ${f(t_1) =}$ undefined and ${f(t_2) =}$ undefined is considered part of ${f}$ being computable in polynomial time. The property of ${s_1,s_2}$ being sources is not necessarily as easy, because ${f}$ need not be invertible in polynomial time. However, the property of ${x}$ not being a source node belongs to the complexity class ${\mathsf{UP}}$, because then there is a unique ${y}$ such that ${f(y) = x}$. The class ${\mathsf{UP}}$ is a subclass of the class into which we will classify this task, so it is unimportant whether ${s_1,s_2}$ being sources is part of the givens or part of the promise.

The property that the graph consists of exactly two paths, however, is the key. If the graph was allowed to consist of many paths, then the problem is easily shown to be polynomial space complete. This makes it all the more surprising that under the promise of being in the two-path case, the complexity of the task drops down to a class that is commonly believed to be lower than polynomial space.

The Complexity of ${\mathsf{TWOPATHS}}$

I do not know the exact complexity of the ${\mathsf{TWOPATHS}}$ problem. The following theorem is the best upper bound that I know:

Theorem: The ${\mathsf{TWOPATHS}}$ problem is in ${\oplus \mathsf{P}}$.

I find this theorem to be unexpected. The obvious algorithm is to iterate the function ${f}$ on ${s_1}$ until an end is reached. Since the paths can be exponentially long, this does not run in polynomial time. Yet the problem can be reduced to the counting class ${\oplus \mathsf{P}}$. Recall this counts the number of accepting computations modulo ${2}$.

The proof is based on ideas that I have already discussed, so I will just give a high-level sketch of the proof.

Suppose we are given the graph ${G}$ defined by the function ${f}$: we know that ${G}$ consists of two paths. The start vertices are ${s_1,s_2}$ and the end vertices are ${t_1,t_2}$. The key idea is to add the edges ${t_1 \rightarrow s_1}$ and ${t_2 \rightarrow s_2}$ to form the graph ${H}$. Then there are two cases: If the path staring with ${s_1}$ ends in ${t_1}$ we get two cycles; if it ends in ${t_2}$ we get one cycle. Thus, to solve the problem we need to decide whether ${H}$ consists of one cycle or two.

This we can do by a trick I discussed before. We can view ${H}$ as defining a permutation on the vertices. The number of inversions of a permutation can be used to tell how many cycles the permutation has modulo ${2}$. But, the number of inversions modulo ${2}$ is easily reduced to a problem that can be computed by ${\oplus \mathsf{P}}$.

The number of inversions is defined as follows as follows: for each pair of vertices ${x}$ and ${y}$ they form an inversion provided

$\displaystyle x < y \mathrm{ \ and \ } f(x) > f(y).$

Finally, why is this only a promise-problem solution? The predicate for counting inversions yields an implicit odd/even number of witnesses for all kinds of graphs. For graphs that did not arise from the promise, the implication for permutations is null and void. Thus the language ${L}$ arising from this predicate belongs to ${\oplus\mathsf{P}}$, but ${L}$ is not restricted to graphs in the promise set ${Q}$. An ordinary language reduces to the promise problem if it reduces to ${L}$, provided the range of the reduction is entirely within ${Q}$. Thus we can say that promise problems are hard for, and even complete for, ordinary complexity classes.

Open Problems

What is the complexity of ${\mathsf{TWOPATHS}}$? Can we prove it is complete for some known class? Can the bound of the theorem be improved? It seems hard to believe that the problem is in, for example, NP. How would guessing help “follow” a path that can be exponentially long?

1. September 5, 2010 11:10 am

Interesting problem. I don’t have time to check the definitions carefully right now (flight to catch!), but what about the following possible proof of Parity-P hardness:

All nodes are of form (x, 0) or (x, 1), where x is a number between 0 and (2^n – 1). Suppose we’re given a polytime-computable Boolean function g on n input bits. Define the function f by

f((x, b)) = (x+1, b) if g(x)=0,

else, f((x, b)) = (x+1, not(b)).

The sources are (0, 0) and (0, 1), and we get a path from (0, 0) to (2^n – 1, 0) iff g has an even number of 1s.

2. September 5, 2010 4:02 pm

So who is Mr. X?

September 5, 2010 4:11 pm

Seems like you can simulate an exponentially long width 2 permutation branching program (which would give two paths) which means TWOPATHS is Parity-P complete.

By a similar logic, the FIVEPATHS program should be PSPACE-complete via Barrington’s theorem.

• September 6, 2010 9:54 pm

Right you are, thanks! To explain as as in the post, instead of thinking of f as the next-configuration function of a space-bounded TM, instead think of a poly-time witness predicate R(x,y). Let the node set be {(y,0),(y,1)} for all y \in {0,1}^m (where m is poly in the length n of x), plus the start nodes s_1 and s_2. Cycle thru each y in order. If R(x,y) holds, crossover the two paths; if not, let them go straight ahead. For the last y, things go to t_1,t_2. Then s_1 goes to t_2 iff the number of y such that R(x,y) holds is odd.

This reduction has range completely within 2-path graphs, so the promise problem is indeed complete for Parity-P. A source for the basic observation is Borodin-Dolev-Fich-Paul, 1986; in particular, this meets their definition of “strict width-2″.

September 5, 2010 4:57 pm

The link in “ideas that I have already discussed _here_” is broken. There’s a trailing “bbb”.

September 5, 2010 5:07 pm

Follow up to previous link-related comment—it looks like that first link shouldn’t be in the post at all, and that it’s the _before_ link that follows that’s intended.

6. September 5, 2010 5:28 pm

I don’t quite understand the analysis. “But, the number of inversions modulo 2 is easily reduced to a problem that can be computed by parity P.” Isn’t the time here in terms of the size of the graph? Isn’t the the size of the graph (whose vertices are bit strings of length n) exponential in n?

• September 7, 2010 7:16 pm

An exponential-sized graph has nodes u,v,w,… whose names are polynomial in length, so it is possible for the edge relation E(u,v) to be “served” in polynomial time. Here we are doing so because E(u,v) is represented as “f(u) = v” for a polynomial-time computable function.

Parity-P, like NP, also involves a nondeterministic Turing machine, or equivalently a polynomial-time decidable witness predicate R(x,y) [with |y| = poly(|x|)]. Such a machine can have a “global” acceptance criterion that depends on the overall number of “locally” accepting computation paths, or equivalently the number of y such that R(x,y) holds. That’s how we can talk about polynomial time in this generally-exponential domain.

September 6, 2010 7:12 am

The link in “The proof is based on ideas that I have already discussed here” seems broken.

September 8, 2010 4:58 pm

September 7, 2010 10:59 am

Well, another predicate became quite interesting to me now :)

x = ?

September 7, 2010 4:51 pm

Well, Wikipedia lists a prominent cryptographer as a former PhD student of Shimon Even…

• September 7, 2010 7:20 pm

There is a notable X for REGAN_Graded_B… —in interest of privacy I’ll say no more :-).

• September 13, 2010 11:53 am
September 8, 2010 9:30 am

And now I am a superstar!

September 8, 2010 9:45 am

Sorry, that was just a joke, to relax. Don’t take it too seriously…