Graphs, Permutations, Characters, and Logspace

July 18, 2009

tags: AC, ACC, Algorithms, character, chess, complete, inversions, logspace, P=NP, permutation, polynomial, Problems, symmetric group

Counting the number of cycles of a permutation with connections to some classic open problems of complexity theory

images

Ken Regan is a great theorist, and probably the best chess player in the world who can really state what P=NP means.

Today I want to talk about a connection between logspace and the computation of the characters of a symmetric group. I also want to show how stupid I can be, which is not fun to point out. However, one of the agendas I had in starting this blog was to show the warts and all in research, and showing my errors is one way to do that. Oh well.

Ken is a very strong chess player. Very. He is an International Master (IM), which is the rank below Grandmaster (GM). His international rating is 2405—ratings in the 2400’s are typical for IM’s, over 2500 for GM’s. I am impressed, when I played in high school my rating started with a 1 and the next digit was not large.

Ken has recently been working on some fascinating projects on detecting cheating in chess tournaments. The issue is simple: is a player using a computer program to help make the moves? As you probably know computer programs are terrific today. Top level programs are matched very well against the best chess players in the world. See for example this. They are especially strong in tactical positions that routinely arise in real matches. So access to a computer would yield a great advantage to the player.

During the 2006 Kramnik-Topalov world championship match cheating accusations against Kramnik were made. Ken was asked to try to decide how one might evaluate such accusations—that a player is making “too many” moves favored by a computer program, in this case the Fritz 9 program. Within days he posted his conclusion that Kramnik’s high coincidence to Fritz and another program, Rybka, was due to the unusually forcing nature of the games, Game 2 in particular. As Ken says,

“If you force play and limit your opponent’s options, don’t be surprised if he matches a computer’s moves!”

See this for further material and details on other cheating controversies and on ratings in general.

Ken deserves a thanks from all chess fans, at all levels, for his quick and insightful analysis of this controversy. Now let’s now turn to logspace and other concerns, and leave behind the coolness of high caliber chess.

Cycle Languages

I need to define a number of languages that will be important for our discussion. All the languages consist of directed graphs with some additional property. The input will always be of the form:

$\displaystyle (x_{1},y_{1}),\dots,(x_{m},y_{m})$

where each ${x_{i}}$ and ${y_{i}}$ is in ${\{ 1,\dots,n \}}$ encoded as binary strings. The meaning of ${(x,y)}$ is that there is a directed edge from ${x}$ to ${y}$ .

The first is the language ${L_{cycle}}$ which consists of all inputs that encode a directed graph that consists of only vertex disjoint cycles. The next languages form a family of languages ${L_{k}}$ and consist of all inputs that contain exactly ${k}$ number of vertex disjoint directed cycles. Note,

$\displaystyle L_{k} \subsetneq L_{cycle}$

for any ${k}$ . Also

$\displaystyle L_{cycle} = L_{1} \cup \dots \cup L_{k} \cup \dots$

Finally, define ${L_{even}}$ to be

$\displaystyle L_{2} \cup L_{4} \cup \dots$

Basic Results

Some definitions are in order. The class ${\mathsf{AC^{0}}}$ is the uniform version of the famous class of constant depth and polynomial size circuits with AND/OR/NOT gates, and the AND/OR gates have unbounded fan-in. Also ${\mathsf{ACC^{0}}[m]}$ is the uniform class that also allows gates that compute mod ${m}$ . The class ${\mathsf{L}}$ denotes logspace. The following two theorems are straightforward.

Theorem: The language ${L_{cycle}}$ is in ${\mathsf{AC^{0}}}$ .

Proof: The key is that a directed graph has this form if and only if the in-degree and out-degree of each vertex is ${1}$ . Clearly, this can be checked as required. For example, the vertex ${v}$ has in-degree at least ${1}$ is equivalent to there is some ${i}$ so that ${(x_{i},y_{i})}$ is an edge and ${v = y_{i}}$ . $\Box$

Theorem: For any ${k \ge 1}$ , the language ${L_{k}}$ is in ${\mathsf{L}}$ .

Logspace Complete Problems

A language is logspace complete, for us, always with respect to ${\mathsf{AC^{0}}}$ reductions. The following theorem and proof is based on Stephen Cook’s and Pierre McKenzie’s classic paper—Problems complete for deterministic logarithmic space.

Theorem: It is ${\mathsf{L}}$ -complete to tell ${L_{1}}$ from ${L_{3}}$ , or any ${L_{k}}$ from ${L_{k+2}}$ . Hence none of these tasks is in ${\mathsf{ACC^{0}[p]}}$ , for any prime ${p}$ .

I have a proof of this theorem, but Ken worked out a better proof. The key parts of the proof were already in Cook-McKenzie, and Ken and Pierre worked out the rest. I thank them for allowing their proof to be included here. If you like you can skip the proof, but Ken worked hard to get all the details right. So please read it now. Or skip it now and come back later on. Or both.

Even Cycle Theorem

So if it’s hard to tell ${1}$ cycle from ${3}$ , how about ${1}$ from ${2}$ , or ${2 }$ from ${3}$ ? Long before I knew ${1}$ from ${3}$ is hard, I proved the following, which seems to be new as far as Ken and Pierre and some others can tell.

Theorem: The language ${L_{even}}$ is in ${\mathsf{ACC^{0}[2]}}$ .

A corollary of this is that ${L_{even}}$ cannot be ${\mathsf{L}}$ complete. This is an unconditional result, because otherwise it would violate known lower bounds on ${\mathsf{ACC^{0}[2]}}$ . More on this in the next section.

Every input that describes a directed graph of disjoint cycles can be viewed as describing a permutation. This is the key to the proof of the theorem. Therefore, we need some basic facts about permutations. While they are simple and classic properties, they are surprisingly useful and powerful.

Each permutation has a value associated with it the number of inversions of the permutation, ${\mathsf{inv}(\pi)}$ . An inversion is a pair of indices ${i,j}$ so that ${i<j}$ and yet ${\pi_{i} > \pi_{j}}$ .

Moreover, the following classic lemma is the key:

Lemma: For any permutation ${\pi}$ on ${n}$ letters,

$\displaystyle \text{number of cycles of } \pi \equiv n + \mathsf{inv}(\pi) \bmod 2.$

We now turn to the proof of the even cycle theorem (ECT):

Proof: Recall that we could view the input graph as a permutation. We want to calculate the parity of the number of cycles. By the above lemma, it is enough to calculate the number of letters and the number of inversions of the permutation. Then, the theorem will follow by the lemma. But, computing each of these is quite simple for a constant depth polynomial circuit that has mod ${2}$ gates. To compute the number of inversions one needs only try all pairs of ${i,j}$ and see if they form an inversion. If they do, count the number of them mod ${2}$ . This completes the proof. $\Box$

I Was Stupid

Quite a while ago I began to look at directed graphs that consisted only of vertex disjoint cycles. I could encode certain problems into this simple class of graphs, and began to try to understand the complexity of telling the number of cycles and other properties.

After a while I realized that they could be viewed as permutations in a natural way. This eventually led me to prove a theorem that was equivalent to the ECT. I then started to think about how to tell how many cycles a permutation had modulo ${4}$ . This seemed, at the time, to be a reasonable possibility. I tried a wide range of tricks. They all were based on the fact that mod ${2}$ gates can compute mod ${4}$ . This is done by a kind of simple amplification trick. So I tried many graph and permutation constructions that attempted to reduce mod ${4}$ to mod ${2}$ .

I had expected the ECT to generalize into statements like this:

${\cup_k L_{4k} \in \mathsf{ACC^{0}[2]}}$

${\cup_k L_{3k} \in \mathsf{ACC^{0}[3]}}$ .

My hope was all in vain, since each of these is impossible. When I say impossible, I mean that these statements are actually false—not just if-horses-can-fly-then-pigs-can-whistle unlikely, but really false. The reason is the brilliant work of Roman Smolensky. I am a bit embarrassed that I took a while—make that a long while—to see the connection with his well known work. I can only say that I guess I got caught in the trees, and could not see the forest. In any event I now understand now what is going on much better.

Recall Smolensky proved that ${\mathsf{ACC^{0}[m]}}$ is not in ${\mathsf{ACC^{0}[p]}}$ when ${p}$ is a prime and ${m}$ is not a power of ${p}$ . So ${\mathsf{ACC^{0}[2]}}$ and ${\mathsf{ACC^{0}[3]}}$ are not in each other, and ${\mathsf{ACC^{0}[6]}}$ is not in ${\mathsf{ACC^{0}[3]}}$ or in ${\mathsf{ACC^{0}[5]}}$ . This is not symmetrical, though—e.g. it does not give you that ${\mathsf{ACC^{0}[5]}}$ is not in ${\mathsf{ACC^{0}[6]}}$ . Indeed, ${\mathsf{ACC^{0}[6]}}$ is a class that gets more annoying every year. It should be small, but we currently cannot even tell that it’s different from NP. Why do we think we can separate P from NP when we cannot even separate it from ${\mathsf{ACC^{0}[6]}}$ ? Thus counting modulo primes versus composites is the frontier of lower bounds, and has been for over two decades. I thought counting cycles would behave like counting 1s in a binary string, but be more important because of how graphs relate to Turing machines.

It should now be clear why ${X}$ and ${Y}$ are impossible. Look at ${X}$ —if it were true, then you could tell ${2}$ cycles apart from ${4}$ cycles. By Theorem that would imply ${\mathsf{ACC^{0}[2]} = \mathsf{L}}$ , which would contradict his famous result. Likewise ${Y}$ would put telling ${1}$ from ${3}$ cycles into ${\mathsf{ACC^{0}[3]}}$ , which is impossible.

Further, if I promise that the input graph ${G}$ is either a single cycle, or is ${3}$ disjoint cycles, with ${\mathsf{ACC^{0}[3]}}$ circuits, can you tell apart these two cases? No. Likewise if I promise ${G}$ forms either ${2}$ cycles or ${4}$ , or ${9}$ versus ${11}$ cycles, the answer is no. However, you can tell ${9}$ versus ${10}$ by ECT.

Characters

There is a way to try to generalize the ECT based on character theory for the symmetric group. This attempt is an approach to prove a theorem like

$\displaystyle \mathsf{ACC^{0}}[6] = \mathsf{L}.$

Or if you think this is false, this approach can be viewed as RCT: reverse complexity theory. What we may be able to prove is that characters of the symmetric group are “hard” to compute.

For us characters will just be mappings from the symmetric group to the integers. A character ${\chi}$ has many properties, but one of the key properties is that if ${\alpha}$ and ${\beta}$ are conjugate permutations, then

$\displaystyle \chi(\alpha) = \chi(\beta).$

Recall two permutations are conjugate if they have the same cyclic structure. Functions that are constant on all permutations with the same cyclic structure are called class functions, since they are constant on a conjugacy class. The characters form a linear basis of the class functions.

Consider the problem of telling apart two permutation types: ${\alpha}$ and ${\beta}$ . Suppose that ${\alpha}$ has one cycle, and ${\beta}$ has three cycles of equal size. The class ${\mathsf{ACC^{0}[2]}}$ cannot tell these apart, for that would again yield an impossible collapse. However, can ${\mathsf{ACC^{0}[6]}}$ , for example, tell them apart? This is the main open question that we are interested in.

Since the characters form a linear basis of the class functions, if ${\alpha}$ and ${\beta}$ are not conjugate permutations, there is a character ${\chi}$ , so that

$\displaystyle \chi(\alpha) \neq \chi(\beta).$

Theorem: Suppose that for ${n}$ , all the characters of the symmetric group on ${n}$ letters can be computed by ${\mathsf{ACC^{0}}[m]}$ , then

$\displaystyle \mathsf{ACC^{0}}[m] = \mathsf{L}.$

I think that this theorem can be greatly strengthened, by carefully calculating which characters are actually needed—needed to tell one cycle from three cycles. Finally, note that one of the characters is always easy to compute:

Lemma: For any permutation ${\pi}$ ,

$\displaystyle \chi_{\text{parity}}(\pi) \equiv \mathsf{inv}(\pi) \bmod 2$

The character ${ \chi_{\text{parity}} }$ is defined as follows. Every permutation can be written as the product of transpositions. Recall a transposition leaves all elements fixed, but switches two elements. A permutation ${\pi}$ can be written in many ways as the product of transpositions, but the parity of the number of transpositions is always the same. Thus, we can assign to ${\pi}$ a value ${\chi_{\text{parity}}(\pi)}$ in ${\{ -1, +1 \}}$ : the value is ${-1}$ for odd permutations and is ${+1}$ for even permutations.

Another way to view this lemma is that there is a summation that computes ${ \chi_{\text{parity}} }$ . For any permutation ${\pi}$ ,

$\displaystyle \chi_{\text{parity}}(\pi) \equiv \sum_{i<j} \, \ulcorner \pi_{i} > \pi_{j} \urcorner \bmod 2.$

Here ${\ulcorner X \urcorner}$ is ${1}$ if ${X}$ is true, and ${0}$ , otherwise. The question, is are there similar summations for any other interesting characters?

There are other characters that are also easy to compute, but they seem to be uninteresting from a complexity point of view. For example, let ${\chi_{\text{fixed}}(\pi)}$ be the number of points that the permutation ${\pi}$ leaves fixed. This is easy to compute too, but does not seem to help.

Open Problems

There are many interesting open questions. First, are there any applications of the ECT? Second, are there some characters that have special formulas like ${ \chi_{\text{parity}} }$ does? I also do not know if ${L_{even}}$ is in ${\mathsf{ACC^{0}[p]}}$ for any odd prime ${p}$ .

The key question is what can we say about the computational cost of computing characters in ${\mathsf{ACC^{0}}[m]}$ for ${m}$ composite? If the answer is that ${\mathsf{ACC^{0}}[m]}$ can compute all characters, then as we observed, that would solve a long standing open problem.

12 Comments leave one →

tcsamateur permalink

July 19, 2009 6:07 am

Nice post!

Regarding the question of whether one can check if $L_{even}$ is in $ACC^0[p]$ for some odd prime $p$ , I wonder if one can resolve this question by reducing Parity to this problem. I think something along these lines might do:

Assume $x\in \{0,1\}^n$ . We want to compute the parity of the bits of $x$ . Consider a graph $G$ with vertices $\{(i,b)\ |\ 1\leq i\leq n+1, b\in \{0,1\}\}$ with the following edges: for $1\leq i \leq n$ and $b\in \{0,1\}$ , add an edge between $(i,b)$ and $(i+1,b')$ if and only if $b' = b\oplus x_i$ ; also add edges between $(n+1,b)$ and $(1,b)$ for each $b$ . Clearly, every vertex in $G$ has indegree and outdegree 1: hence, it is a union of vertex disjoint cycles. Moreover, the number of cycles is either 1 or 2, and 1 if and only if the parity of the bits of $x$ is 1.

Loading...

Reply
- Alex Nikolov permalink
  
  July 19, 2009 12:56 pm
  
  Nice reduction!
  
  Loading...
  
  Reply
Anon permalink

July 19, 2009 8:42 am

Prof. Lipton,

One formula does not parse, in the paragraph right after the last lemma. I know it is -1 (if you move the mouse over the formula). Thanks, as usual, for a very informative entry.

Loading...

Reply
none permalink

July 19, 2009 11:17 pm

Jim Tarjan (CS theorist Bob Tarjan’s brother) might know what P vs Np is, and is a rather strong GM, does that count?

Loading...

Reply
Kenneth Regan permalink

July 20, 2009 3:02 pm

Funnily enough, I mentioned Jim Tarjan in e-mail to Dick in exactly that context. I think what he meant by “really”, however, is being conversant with the deeper issues around P =? NP such as Dick has discussed them on this blog. In the next rank (Master, 2200–2400) there are several to whom I absolutely must tip my cap, among them Noam Elkies and Stephen Smale.

Nice reduction indeed, tcsamateur! I had missed that question at the end. Another open technical matter is extending the main reduction to showing the hardness of telling k vs. k+4, k+6 etc. The main question is whether there are any nice applications. And *why* does it only happen for parity—because 2 is the only even prime? because the permanent and hence related graph-counting problems are easy mod 2?

Loading...

Reply

	rjlipton on The 100th anniversary of Fulke…
	Gabriel Verret on The 100th anniversary of Fulke…
	Blog Runner on The 100th anniversary of Fulke…
	JG on The 100th anniversary of Fulke…
	T.D. Nguyen on Just Jim
	joe12361 on Just Jim
	T Nguyen on COMPUTATION, LOGIC, AND INFORM…
	Umayr on 1968 vs 2024
	javaid aslam on 1968 vs 2024
	Ian Z aka nobrowser on 1968 vs 2024
	Enough is enough on 1968 vs 2024
	rjlipton on An Open Problem
	Jordan on An Open Problem
	Jon Awbrey on An Open Problem
	Blog Runner on An Open Problem

a personal view of the theory of computation

Graphs, Permutations, Characters, and Logspace

Like this:

Related

Trackbacks

Leave a ReplyCancel reply

Subscribe to Gödel’s Lost Letter

Our Book

Recent Posts

Top Posts

Recent Comments

Blogroll

Archives

Sitemeter

a personal view of the theory of computation

Graphs, Permutations, Characters, and Logspace

Share this:

Like this:

Related

Trackbacks

Leave a ReplyCancel reply

Subscribe to Gödel’s Lost Letter

Our Book

Recent Posts

Top Posts

Recent Comments

Blogroll

Archives

Sitemeter

Discover more from Gödel's Lost Letter and P=NP