The

Computational

Complexit

y

Column

b

y

Jaob

o

T

o

rán

Dept.

Theoretis

he

Informatik,

Univ

ersität

Ulm

Ob

erer

Eselsb

erg,

89069

Ulm,

German

y

toraninformatik.uni

-

ulm

.de

http://theorie.inform

ati

k.u

ni-

ulm.

de/

Per

son

en/

jt.

htm

l

Isomorphism

Testing:

Perspetive

and

Open

Pr

oblems

V.

Arvind

Jaob

o

T

orán

y

Abstrat

F

or

o

v

er

three

deades

the

graph

isomorphism

problem

has

tan-

talized

resear

hers

in

algorithms

and

omplexit

y

.

The

study

of

this

problem

has

stim

ulated

a

lot

of

resear

h

and

has

led

to

the

diso

v

ery

of

imp

ortan

t

onepts

in

the

area.

In

this

artile

w

e

tak

e

a

fresh

lo

ok

at

isomorphism

problems

and

highligh

t

some

op

en

questions.

Institute

of

Mathematial

Sienes,

C.

I.

T.

Campus,

Chennai

600

113,

India

Email:

arvindims.res.i

n

y

Abt.

Theoretis

he

Informatik,

Univ

ersität

Ulm,

Ob

erer

Eselsb

erg,

89069

Ulm,

Ger-

man

y

.

Email:

toraninformati

k.

uni

-u

lm

.de

1

In

tro

dution

The

graph

isomorphism

problem,

GI,

onsists

in

deiding

whether

t

w

o

giv

en

graphs

are

isomorphi.

In

other

w

ords,

the

problem

is

to

test

whether

there

is

a

bijetiv

e

funtion

mapping

the

v

erties

of

the

rst

graph

to

the

no

des

of

the

seond

graph

and

preserving

the

adjaeny

relation.

GI

has

reeiv

ed

onsiderable

atten

tion

sine

it

is

one

of

the

few

problems

in

NP

that

is

nei-

ther

kno

wn

to

b

e

omputable

in

p

olynomial

time

nor

to

b

e

NP-omplete.

GI

is

the

b

est-kno

wn

example

of

a

family

of

isomorphism

problems

on

algebrai

strutures

lik

e

groups

and

rings

that

ha

v

e

a

similar

in

termediate

status,

b

e-

t

w

een

P

and

NP-omplete.

Isomorphism

questions

ha

v

e

pro

v

ed

in

the

past

to

b

e

an

imp

ortan

t

to

ol

for

exploring

the

tigh

t

in

terpla

y

b

et

w

een

omputational

problems

and

omplexit

y

lasses.

Often,

these

problems

do

not

quite

t

in

standard

omplexit

y

lasses,

in

terms

of

ompleteness

for

example.

The

study

of

this

p

euliarit

y

has

motiv

ated

imp

ortan

t

adv

anes

in

omplexit

y

theory:

Arth

ur-Merlin

games,

lo

wness,

in

terativ

e

pro

of

systems,

oun

ting

lasses

or

derandomization.

F

rom

an

algorithmi

p

ersp

etiv

e,

the

attempts

at

diso

v-

ering

a

p

olynomial-time

algorithm

for

graph

isomorphism

has

enri

hed

the

eld

with

algebrai

te

hniques,

partiularly

from

the

theory

of

p

erm

utation

groups.

In

this

olumn

w

e

briey

surv

ey

the

status

of

some

imp

ortan

t

op

en

ques-

tions

related

to

isomorphisms

of

graphs

(also

rings

and

groups).

W

e

do

not

attempt

to

b

e

omprehensiv

e.

Rather,

our

goal

is

to

fo

us

on

a

few

topis

and

to

iden

tify

in

teresting

op

en

questions

for

whi

h,

hop

efully

,

the

answ

ers

do

not

lie

to

o

far

b

ey

ond

rea

h.

In

a

brief

surv

ey

of

this

nature

it

is

diult

to

tou

h

up

on

ramiations

of

the

area

in

omputational

group

theory

,

whi

h

is

a

sub

jet

b

y

itself.

Also,

a

ertain

bias

due

to

our

resear

h

in

terests

in

omplexit

y

theory

is

una

v

oidable.

2

Preliminaries

By

graphs

w

e

mean

nite

simple

graphs,

usually

denoted

b

y

X

=

(V

;

E

),

where

V

is

the

v

ertex

set

and

E

V

2

.

W

e

sa

y

t

w

o

graphs

X

1

and

X

2

are

isomorphi

if

there

is

a

bijetion

'

:

V

1

!

V

2

su

h

that

(u;

v

)

2

E

1

i

('(u);

'(v

))

2

E

2

.

W

e

write

X

1

=

X

2

and

all

'

an

isomorphism.

An

au-

tomorphism

of

a

graph

X

is

an

isomorphism

from

X

to

X

.

Automorphisms

are

p

erm

utations

on

the

set

V

,

and

the

set

of

automorphisms

Aut(X)

forms

a

group

under

p

erm

utation

omp

osition.

More

preisely

,

if

jV

j

=

n

then

Aut(X)

is

a

subgroup

of

S

n

the

symmetri

group

on

n

elemen

ts.

It

is

w

ell

kno

wn

that

graph

isomorphism

testing

is

p

olynomial

time

equiv

alen

t

to

nd-

ing

a

p

olynomial-size

generator

set

for

the

automorphism

group

of

a

graph.

W

e

no

w

reall

some

relev

an

t

p

erm

utation

group

theory

.

In

general,

Sym()

denotes

the

symmetri

group

on

the

nite

set

.

A

p

ermutation

gr

oup

on

is

a

subgroup

of

Sym().

F

or

jj

=

n,

w

e

let

=

[n℄

and

simply

write

S

n

of

all

p

erm

utations

on

[n℄

=

f1;

2

:

:

:

;

ng

to

denote

Sym().

Giv

en

g

2

S

n

and

i

2

[n℄,

w

e

denote

b

y

i

g

the

image

of

i

under

p

erm

utation

g

.

This

a

on

v

enien

t

notation

to

express

the

left

to

righ

t

omp

osition

g

1

g

2

of

p

erm

utations

g

1

;

g

2

2

S

n

.

More

preisely

,

w

e

an

write

i

g

1

g

2

=

(i

g

1

)

g

2

for

all

i

2

[n℄.

F

or

[n℄

and

g

2

S

n

w

e

write

g

for

its

image

under

g

:

g

=

fj

j

j

=

i

g

g.

F

or

[n℄,

G

()

denotes

the

subgroup

of

G

that

xes

ea

h

elemen

t

of

,

and

G

denotes

the

subgroup

fg

2

G

j

g

=

g.

The

p

erm

utation

group

gener

ate

d

b

y

a

subset

A

of

S

n

is

the

smallest

subgroup

of

S

n

on

taining

A

and

is

denoted

hAi.

W

e

assume

that

subgroups

of

S

n

are

presen

ted

b

y

generator

sets.

Sine

an

y

nite

group

G

has

a

generator

set

of

size

log

jGj,

subgroups

of

S

n

ha

v

e

generator

sets

of

size

p

olynomial

in

n.

The

iden

tit

y

p

erm

utation

is

denoted

b

y

1

(w

e

use

1

to

denote

the

iden

tit

y

of

all

groups).

F

or

a

subgroup

G

of

S

n

(denoted

G

S

n

)

the

set

i

G

=

fi

g

j

g

2

Gg

for

i

2

[n℄

is

the

G-orbit

of

i,

and

G

is

tr

ansitive

on

[n℄

if

i

G

=

[n℄

for

i

2

[n℄.

Let

G

Sym()

b

e

transitiv

e

on

.

A

G-blo

k

is

a

subset

of

[n℄

su

h

that

for

ev

ery

g

2

G

either

g

=

or

g

\

=

;.

F

or

a

transitiv

e

group

G,

the

set

[n℄

and

the

singleton

sets

fig,

i

2

[n℄

are

trivial

blo

ks.

A

transitiv

e

group

G

is

primitive

if

it

do

es

not

ha

v

e

an

y

non

trivial

blo

ks

otherwise

it

is

alled

imprimitive.

Let

G

1

and

G

2

b

e

t

w

o

nite

groups.

W

e

sa

y

that

G

1

and

G

2

are

isomorphi

if

there

is

a

bijetion

'

:

G

1

!

G

2

that

preserv

es

the

group

op

eration.

Lik

ewise,

for

t

w

o

nite

rings

R

1

and

R

2

,

w

e

sa

y

that

they

are

isomorphi

if

there

is

a

bijetion

'

:

R

1

!

R

2

that

preserv

es

the

ring

op

erations.

As

for

graphs,

automorphisms

are

isomorphisms

from

an

algebrai

struture

to

itself,

and

the

automorphisms

form

a

group

under

the

omp

osition

op

eration.

W

e

briey

reall

the

denitions

and

notation

for

some

standard

om-

plexit

y

lasses.

Details

an

b

e

found

in

a

textb

o

ok

lik

e

[14

℄.

Let

P

denote

the

lass

of

languages

(deision

problems)

that

are

aepted

b

y

deterministi

T

uring

ma

hines

in

time

b

ounded

b

y

a

p

olynomial

in

input

size,

and

NP

de-

note

the

lass

of

languages

aepted

b

y

nondeterministi

T

uring

ma

hines

in

p

olynomial

time.

W

e

denote

the

lass

of

funtions

omputable

in

p

olynomial

time

b

y

FP

.

A

funtion

f

:

f0;

1g

!

N

is

said

to

b

e

in

the

oun

ting

lass

#P

if

there

is

a

p

olynomial

time

nondeterministi

T

uring

ma

hine

M

su

h

that

f

(x)

is

the

n

um

b

er

of

aepting

paths

of

M

on

input

x.

A

funtion

f

in

the

lass

FP

A

is

omputable

b

y

p

olynomial-time

deter-

ministi

or

ale

T

uring

ma

hine

M

whi

h

has

aess

to

orale

A:

M

an

en

ter

a

sp

eial

query

state

and

query

the

mem

b

ership

of

a

string

y

in

A.

W

e

an

similarly

dene

FP

f

for

a

funtion

orale

f

.

Let

C

b

e

a

relativizable

omplexit

y

lass.

A

language

A

is

said

to

b

e

low

for

C

if

C

A

=

C

.

3

Hardness

GI

has

sev

eral

prop

erties

that

are

not

kno

wn

to

hold

b

y

NP-omplete

prob-

lems.

F

or

example,

the

oun

ting

v

ersion

of

GI

is

reduible

to

its

deision

v

ersion

[28

℄.

Moreo

v

er,

it

is

kno

wn

that

graph

non-isomorphism,

the

om-

plemen

t

of

GI,

b

elongs

to

the

lass

AM

of

deision

problems

whose

y

es

instanes

ha

v

e

short

mem

b

ership

pro

ofs

in

a

probabilisti

sense

[7

℄.

This

implies

that

if

the

problem

w

ere

NP-omplete,

then

the

p

olynomial

time

hi-

erar

h

y

w

ould

ollapse

to

its

seond

lev

el

[15,

34℄.

Beause

of

these

fats,

w

e

do

not

b

eliev

e

that

GI

is

NP-omplete.

On

the

other

hand

GI

is

not

kno

wn

to

b

e

in

P

and

w

e

migh

t

ask

what

is

the

largest

omplexit

y

lass

C

for

whi

h

w

e

an

pro

v

e

that

GI

is

hard

for

C

?

Or

more

sp

eially:

Problem

1.

Is

GI

har

d

for

P?

The

rst

hardness

results

for

GI

w

ere

giv

en

in

[20℄

where

it

w

as

sho

wn

that

GI

is

hard

for

NC

1

the

lass

of

problems

omputable

b

y

uniform

ir-

uit

families

of

p

olynomial

size

and

logarithmi

depth,

and

for

L,

logarithmi

spae.

The

hardness

for

NC

1

is

pro

v

ed

b

y

essen

tially

sim

ulating

a

logarith-

mi

depth

iruit

with

AND

and

OR

gates

b

y

an

isomorphism

question.

F

or

ea

h

gate

g

in

the

iruit,

a

pair

of

graphs

(G

g

;

H

g

)

is

onstruted

in

su

h

a

w

a

y

that

the

graphs

are

isomorphi

if

and

only

if

the

gate

has

v

alue

1.

This

is

easy

to

do

for

the

input

gates.

F

or

the

iruit

gates,

the

AND

and

OR

funtions

for

GI

are

used.

An

AND

funtion

for

a

problem

A

is

a

funtion

f

that

is

easy

to

ompute

and

su

h

that

on

input

x;

y

,

f

(x;

y

)

2

A

if

and

only

if

x

2

A

AND

y

2

A.

The

OR

funtion

is

dened

analogously

.

It

is

kno

wn

that

GI

has

AND

and

OR

funtions.

This

prop

ert

y

an

b

e

used

as

sk

et

hed

ab

o

v

e

to

nally

build

a

pair

of

graphs

(G;

H

)

orresp

onding

to

the

output

gate,

su

h

that

they

are

isomorphi

if

and

only

if

the

iruit

outputs

1.

A

natural

question

is:

wh

y

annot

this

metho

d

b

e

applied

to

similarly

sim

u-

late

p

olynomial-size

monotone

iruits?

If

this

w

ere

p

ossible

it

w

ould

follo

w

that

GI

is

hard

for

P

.

Unfortunately

,

the

diult

y

lies

with

the

kno

wn

OR

funtion

onstrution

for

GI:

the

OR

funtion

doubles

the

size

of

its

inputs.

Therefore,

in

order

to

k

eep

the

output

of

the

redution

p

olynomial

in

size,

the

ab

o

v

e

metho

d

an

only

b

e

applied

to

for

iruits

ha

ving

a

logarithmi

n

um

b

er

of

OR-gates

in

an

y

path

from

an

input

to

the

output

gate.

A

natural

question

in

this

on

text

is

the

follo

wing.

Problem

2.

Do

es

gr

aph

isomorphism

have

an

eiently

omputable

OR

funtion

f

suh

that

f

(x;

y

)

has

size

at

most

(jxj

+

jy

j),

wher

e

<

2?

The

hardness

results

for

GI

from

[20

℄

w

ere

impro

v

ed

in

[35℄

to

other

omplexit

y

lasses

using

a

dieren

t

metho

d.

In

order

to

sim

ulate

a

ertain

kind

of

iruit

gate

g

with

inputs

x

and

y

,

a

graph

gadget

is

onstruted

ha

ving

some

v

erties

related

to

the

inputs

of

g

and

some

v

erties

related

to

the

outputs.

An

automorphism

in

the

gadget

graph

with

ertain

restritions

eno

ding

the

input

v

alues

of

g

is

fored

to

map

the

no

des

related

to

the

output

in

a

w

a

y

eno

ding

g

(x;

y

).

An

example

of

su

h

a

gadget

eno

ding

a

parit

y

gate

is

giv

en

in

Figure

1.

y

x

z

b

b

b

b

b

b

b

b

b

b

x

0

x

1

y

0

y

1

u

1;1

u

1;0

u

0;1

u

0;0

z

0

z

1

Figure

1:

A

graph

gadget

sim

ulating

a

parit

y

gate.

F

or

the

-gate

onsidered

in

the

gure,

the

input

v

alues

an

b

e

eno

ded

in

the

gadget

graph

automorphism

as

follo

ws:

if

x

has

v

alue

a

2

f0;

1g

then

w

e

restrit

the

set

of

onsidered

automorphisms

to

those

mapping

v

ertex

x

0

to

x

a

,

and

the

same

for

y

.

It

is

not

hard

to

see

that

an

y

automorphism

mapping

x

0

to

x

a

and

y

0

to

y

b

for

a;

b

2

f0;

1g,

m

ust

map

z

0

to

z

ab

th

us

omputing

the

output

of

the

gate.

A

gadget

is

onstruted

for

ea

h

gate

and

they

are

onneted

as

in

the

iruit.

The

onstruted

graph

has

an

automorphism

of

the

kind

eno

ding

the

input

v

alues

of

the

iruit

and

mapping

the

output

v

ertex

to

a

v

ertex

eno

ding

v

alue

1

if

and

only

if

the

v

alue

pro

dued

b

y

the

iruit

is

1.

This

question

an

b

e

redued

to

GI.

In

[35

℄

it

is

sho

wn

that

su

h

graph

gadgets

an

b

e

onstruted

for

ev

ery

mo

dular

addition

gate.

More

generally

,

for

an

y

omm

utativ

e

group

this

gadget

an

sim

ulate

the

group

op

eration.

But

this

do

es

not

seem

to

sue

for

apturing

the

whole

lass

P

.

It

is

kno

wn

that

the

iruit

v

alue

problem

for

p

olynomial

size

iruits

with

gates

omputing

m

ultipliation

in

S

5

,

the

group

of

p

erm

utations

o

v

er

v

e

elemen

ts,

is

omplete

for

P

.

But

S

5

is

not

an

ab

elian

group,

and

therefore

the

te

hnique

from

[35℄

annot

b

e

applied

here.

The

largest

omplexit

y

lass

kno

wn

to

b

e

reduible

to

GI

is

DET

[35℄,

the

lass

of

problems

that

are

NC

1

reduible

to

omputing

the

in

teger

de-

terminan

t

[16

℄.

DET

b

elongs

to

NC

2

and

therefore

there

is

still

a

large

gap

for

pro

ving

hardness

of

GI

for

P

.

An

immediate

and

natural

op

en

question

is

whether

GI

is

hard

for

LOGCFL

(LOGCFL

is

the

sub

lass

of

NC

2

onsisting

of

problems

that

are

logspae

reduible

to

a

on

text-free

language).

Problem

3.

Is

gr

aph

isomorphism

har

d

for

LOGCFL

?

A

dieren

t

approa

h

to

mak

e

progress

on

this

problem

is

to

onsider

iso-

morphism

of

other

algebrai

strutures

(see

Setion

6

where

w

e

onsider

some

of

these

in

detail).

Problems

lik

e

ring

isomorphism

and

group

isomorphism

app

ear

to

b

e

harder

than

GI.

It

should

b

e

easier

to

sho

w

that

these

are

hard

for

P.

Problem

4.

A

r

e

the

isomorphism

pr

oblems

for

rings,

p

ermutation

gr

oups

or

blak-b

ox

gr

oups

har

d

for

P?

4

Graph

Isomorphism

for

Restrited

Classes

The

graph

isomorphism

problem

for

ertain

sp

eial

lasses

of

graphs

is

kno

wn

to

ha

v

e

p

olynomial-time

algorithms.

One

su

h

restrition

that

is

w

ell-studied

is

the

b

ounde

d

olor

multipliity

gr

aph

isomorphism

problem

(BCGI

b

):

for

a

pair

of

v

ertex-olored

graphs

(G

1

;

G

2

)

su

h

that

there

are

at

most

a

onstan

t

b

man

y

v

erties

of

an

y

giv

en

olor

in

ea

h

graph,

test

if

there

is

a

olor-

preserving

isomorphism

b

et

w

een

G

1

and

G

2

.

Luks

in

[26℄

ga

v

e

a

remark

able

NC

algorithm

for

the

BCGI

b

problem.

On

the

other

hand,

w

e

an

see

that

sev

eral

of

the

hardness

results

for

GI

[35

℄

(see

Setion

3)

are

hardness

results

for

BCGI

b

.

More

preisely

,

it

is

kno

wn

that

BCGI

b

is

A

C

0

-man

y

one

hard

for

the

logspae

oun

ting

lass

Mo

dk

for

ea

h

onstan

t

k

.

The

onstrution

in

[35℄

requires

b

to

b

e

k

2

.

Building

on

[26℄,

in

[5℄

the

gap

b

et

w

een

the

upp

er

and

lo

w

er

b

ound

results

for

BCGI

b

is

in

some

sense

losed

b

y

pro

ving

that

BCGI

b

is

in

Mo

dk

hierar

h

y

and

noting

that

the

hardness

results

for

BCGI

b

extend

to

the

Mo

dk

hierar

h

y

,

where

the

onstan

t

k

and

the

lev

el

of

the

hierar

h

y

in

whi

h

BCGI

sits

dep

ends

on

b.

Tigh

t

haraterizations

are

also

kno

wn

for

tree

isomorphism

in

t

w

o

dif-

feren

t

represen

tations

(see

e.g.

[20

℄

for

this

and

other

examples).

This

op

ens

up

similar

omplexit

y-theoreti

questions

for

other

lasses

of

graphs

for

whi

h

GI

has

a

p

olynomial-time

algorithm.

The

problem

is

to

preisely

lassify

the

restrited

problem

inside

P

b

y

giving

mat

hing

upp

er

and

lo

w

er

b

ounds.

Reall

that

inside

P

there

is

a

ri

h

tap

estry

of

natural

omplexit

y

lasses.

P

artiularly

,

natural

problems

lik

e

omputing

in

teger

de-

terminan

t

ab

ound

within

NC

2

;

the

lassiation

of

these

problems

are

mainly

a

result

of

insigh

ts

in

to

logspae

oun

ting

lasses

(see

e.g.

the

surv

ey

artile

[2℄).

Th

us

it

is

natural

to

seek

the

preise

lassiation

of

restrited

v

ersions

of

GI.

Notable

examples

are

(i)

graphs

of

b

ounded

degree

[25℄,

(ii)

graphs

of

b

ounded

gen

us

[29℄,

and

(iii)

graphs

of

b

ounded

eigen

v

alue

m

ultipliit

y

[11

℄

whi

h

all

ha

v

e

p

olynomial

time

algorithms

for

GI.

Of

these,

w

e

fo

us

on

graph

isomorphism

for

b

ounded

degree

graphs

(BDGI),

where

the

maxim

um

degree

of

the

input

graphs

is

b

ounded

b

y

a

onstan

t.

Luks

in

[25℄

ga

v

e

a

p

olynomial-time

algorithm

for

this

problem.

This

pap

er

w

as

a

ma

jor

breakthrough,

in

tro

duing

metho

ds

from

p

erm

uta-

tion

group

theory

whi

h

ha

v

e

sine

b

eome

en

tral

te

hniques

in

the

area

of

isomorphism

testing

as

w

ell

as

in

the

design

of

p

erm

utation

group

algorithm.

Ho

w

ev

er,

it

is

still

op

en

if

BDGI

is

in

NC

(or

ev

en

RNC).

Luks

has

observ

ed

in

[26℄

that

BDGI

an

b

e

NC

redued

to

the

set-

stabilizer

problem

for

groups

in

d

.

W

e

reall

the

denitions

to

in

tro

due

the

ideas

in

v

olv

ed.

Denition

1.

A

nite

gr

oup

G

is

said

to

b

e

in

the

lass

d

if

for

any

om-

p

osition

series

G

=

G

0

G

1

:

:

:

G

t

=

1

e

ah

omp

osition

fator

G

i

=G

i+1

is

either

ab

elian

or

is

isomorphi

to

a

sub

gr

oup

of

S

d

.

The

lass

d

of

nite

groups

is

algorithmially

imp

ortan

t.

It

has

pla

y

ed

an

imp

ortan

t

role

in

pro

ving

time

b

ounds

for

sev

eral

p

erm

utation

group

algorithms,

inluding

the

urren

t

b

est

algorithm

for

the

graph

isomorphism

problem

(e.g.

see

[27℄).

Giv

en

a

p

erm

utation

group

G

S

n

b

y

a

generating

set

A

and

a

subset

of

f1;

2;

;

ng,

the

set

stabilizer

pr

oblem

is

to

ompute

a

generating

set

for

the

stabilizer

group

G

.

Set

stabilizer

is

of

in

terest

b

eause

GI

is

reduible

to

it.

T

o

see

it

note

that

it

sues

to

sho

w

that

nding

the

automorphism

group

is

reduible

to

set

stabilizer.

F

or

a

graph

X

=

(V

;

E

),

let

G

=

S

n

at

on

the

pairs

V

2

where

jV

j

=

n.

Clearly

,

for

=

E

w

e

ha

v

e

G

is

Aut(X).

Prop

osition

2.

Gr

aph

isomorphism

is

p

olynomial-time

r

e

duible

to

set

sta-

bilizer.

A

more

in

v

olv

ed

redution

in

[26℄

sho

ws

that

BDGI

is

NC

reduible

to

p

erm

utation

groups

in

d

.

Therefore,

one

w

a

y

to

put

BDGI

in

NC

w

ould

b

e

to

sho

w

that

the

set

stabilizer

problem

is

in

NC.

Problem

5.

Pr

e

isely

lassify

the

omplexity

of

the

set

stabilizer

pr

oblem

for

gr

oups

in

d

(or

even

solvable

gr

oups).

It

follo

ws

from

the

results

of

Babai,

Luks,

and

Séress

[11

,

8

℄

that

graph

isomorphism

for

the

b

ounded

eigen

v

alue

m

ultipliit

y

ase

is

in

NC.

Problem

6.

Classify

the

omplexity

of

gr

aph

isomorphism

for

gr

aphs

with

b

ounde

d

eigenvalue

multipliity.

5

Graph

Canonization

Let

G

n

denote

the

set

of

all

simple

undireted

graphs

on

n

v

erties.

A

an-

onizing

funtion

for

G

n

is

a

funtion

f

from

G

n

to

G

n

su

h

that

F

or

an

y

graph

G

2

G

n

,

f

(G)

is

isomorphi

to

G.

F

or

G

1

;

G

2

2

G

n

,

f

(G

1

)

=

f

(G

2

)

if

and

only

if

G

1

is

isomorphi

to

G

2

.

In

other

w

ords,

a

anonizing

funtion

assigns

a

anoni

al

form

to

ea

h

iso-

morphism

lass

of

graphs.

F

or

example,

the

funtion

f

su

h

that

f

(G)

is

the

lexiographially

least

graph

in

the

isomorphism

lass

on

taining

G

is

a

anonizing

funtion.

Ho

w-

ev

er,

as

observ

ed

in

[10

,

27℄,

this

anonizing

funtion

is

NP-hard.

Notie

that

this

funtion

an

b

e

omputed

in

FP

NP

b

y

a

simple

prex

sear

h

algorithm.

The

in

triguing

op

en

question

is

whether

there

is

some

anonizing

fun-

tion

for

graphs

that

an

b

e

omputed

in

p

olynomial

time.

No

b

etter

upp

er

b

ound

than

FP

NP

is

kno

wn

for

general

graphs

(for

an

y

anonizing

funtion).

Th

us,

it

is

a

basi

omplexit

y-theoreti

question

to

lassify

the

omplexit

y

of

anonization.

Is

this

problem

lo

w

for

an

y

lev

el

of

the

p

olynomial

hierar

h

y?

W

e

note

that

obtaining

anonial

forms

for

algebrai

ob

jets

is

a

natural

and

fruitful

pursuit

in

mathematis.

F

or

instane,

w

e

ha

v

e

the

Jordan

Canon-

ial

F

orm

for

matries

under

similarit

y

transformations.

Lik

ewise,

w

e

ha

v

e

the

Hermite

Normal

F

orm

for

latties

under

unimo

dular

transformations.

These

normal

forms

an

pla

y

an

imp

ortan

t

role

in

the

design

of

eien

t

algorithms

for

problems.

On

rst

sigh

t

it

w

ould

app

ear

that

graph

anonization

is

losely

related

to

the

problem

of

isomorphism

testing.

Indeed,

for

one

diretion

w

e

an

observ

e

that

isomorphism

testing

for

graphs

is

p

olynomial-time

reduible

to

graph

anonization.

Ho

w

ab

out

the

on

v

erse?

Problem

7.

Is

gr

aph

anonization

p

olynomial

time

r

e

duible

to

gr

aph

iso-

morphism?

There

is

in

teresting

evidene

supp

orting

a

p

ositiv

e

answ

er

in

the

results

of

Babai

and

Luks

[10℄.

Building

on

the

earlier

seminal

w

ork

of

Luks

[25℄,

Babai

and

Luks

tak

e

an

algebrai

approa

h

to

the

anonization

problem.

W

e

reall

some

denitions

b

efore

w

e

explain

a

k

ey

result

in

their

pap

er.

First

w

e

an

assume

b

y

eno

ding

that

w

e

are

w

orking

with

strings

(o

v

er

a

nite

alphab

et,

sa

y

f0;

1g)

as

our

ob

jets

instead

of

graphs.

Let

G

S

n

b

e

a

subgroup

of

the

symmetri

group

ating

on

f0;

1g

n

as

follo

ws:

for

a

p

erm

utation

g

2

G

and

x

=

x

1

x

2

x

n

2

f0;

1g

n

,

g

maps

x

to

y

(denoted

x

g

=

y

),

where

y

=

x

i

1

x

i

2

x

i

n

su

h

that

i

k

=

k

g

for

1

k

n.

No

w,

the

general

problem

an

b

e

stated

as

follo

ws:

W

e

sa

y

that

t

w

o

strings

x

and

y

are

G-isomorphi

if

x

g

=

y

for

some

g

2

G.

W

e

sa

y

that

f

:

f0;

1g

n

!

f0;

1g

n

is

a

anonizing

funtion

w.r.t.

the

group

G,

if

f

(x)

and

x

are

G-isomorphi

for

all

x

and

f

(x)

=

f

(y

)

i

x

and

y

are

G-isomorphi.

In

an

y

ase,

lexiographi

anonization

remains

hard

ev

en

for

v

ery

simple

groups

G.

Prop

osition

3.

[10℄

The

lexi

o

gr

aphi

anonizing

funtion

w.r.t.

arbitr

ary

gr

oups

G

for

strings

is

NP -har

d

even

if

G

is

r

estrite

d

to

b

e

an

elementary

ab

elian

2-gr

oup.

The

idea

of

the

pro

of

is

to

giv

e

a

p

olynomial-time

redution

from

the

maxim

um

lique

problem

to

the

lexiographi

anonization

problem.

More

imp

ortan

t,

on

the

p

ositiv

e

side,

Babai

and

Luks

giv

e

an

algorithm

for

omputing

a

anonizing

funtion

that

dep

ends

on

the

struture

of

the

group

G.

This

algorithm

is

based

on

a

divide-and-onquer

strategy

along

the

same

lines

as

dev

elop

ed

b

y

Luks

in

[25

℄:

the

divide

and

onquer

is

done

on

the

group

G

based

on

its

in

ternal

struture

(transitiv

e

onstituen

ts,

primitivit

y

and

imprimitivit

y

struture).

If

G

is

a

p

erm

utation

group

in

the

lass

d

,

it

turns

out

that

this

anon-

ization

algorithm

runs

in

p

olynomial

time.

Cruially

,

the

fat

that

primitiv

e

groups

in

d

are

of

size

at

most

n

O

(d)

is

used

for

this

analysis.

T

o

summarize:

Theorem

4.

[10℄

Given

a

gr

oup

G

S

n

suh

that

G

2

d

,

ther

e

is

an

n

O

(d)

algorithm

that

omputes

a

anonizing

funtion

for

G

n

.

In

[10

℄

it

is

also

sho

wn

that

for

general

graphs

there

is

a

n

1=2+o(1)

anon-

izing

algorithm

whi

h

losely

mat

hes

the

running

time

of

the

b

est

kno

wn

isomorphism

test

for

general

graphs.

Ho

w

ev

er,

from

a

omplexit

y-theoreti

p

oin

t

of

view

the

relativ

e

diult

y

is

not

lear

ev

en

for

the

problem

of

G-

isomorphism

testing

for

a

group

G

2

d

.

In

partiular,

w

e

w

ould

lik

e

to

kno

w

an

answ

er

for

the

follo

wing

question.

W

e

onjeture

that

the

answ

er

should

b

e

p

ositiv

e.

Problem

8.

L

et

G

S

n

b

e

a

p

ermutation

gr

oup

that

is

in

d

.

Is

the

pr

ob-

lem

of

testing

if

two

strings

x

and

y

ar

e

G-isomorphi

NC

e

quivalent

to

the

orr

esp

onding

anonization

pr

oblem?

W

e

an

also

ask

a

similar

question

for

solvable

p

ermutation

gr

oups,

whih

is

a

sub

lass

of

d

.

A

more

general

problem

is

the

follo

wing.

Problem

9.

F

or

dier

ent

r

estrite

d

gr

aph

lasses

onsider

e

d

in

Se

tion

4,

what

is

the

r

elative

omplexity

of

isomorphism

and

anonization?

W

e

next

briey

disuss

anonization

for

nite

groups

and

rings.

What

is

the

appropriate

notion

for

groups?

F

or

ab

elian

groups,

the

struture

theorem

deomp

osing

an

y

nite

ab

elian

group

in

to

a

diret

pro

dut

of

yli

groups

is

a

natural

anonial

form

and

it

an

b

e

used

to

test

the

isomorphism

of

t

w

o

ab

elian

groups.

Th

us,

the

problem

of

anonization

for

nite

ab

elian

groups

b

oils

do

wn

to

omputing

the

yli

group

deomp

osition.

Of

ourse,

the

question

arises

whether

there

ould

b

e

anonial

forms

that

are

e

asier

to

ompute.

F

or

nonab

elian

groups,

it

do

es

not

app

ear

that

there

is

an

y

su

h

in

trinsi

anonial

form.

It

is

tempting

to

use

the

omp

osition

series

(or

some

other

series

for

groups)

but

these

are

only

partial

isomorphism

in-

v

arian

ts.

Of

ourse,

the

lexiographi

anonial

form

an

alw

a

ys

b

e

dened

for

nite

groups

(and

rings).

But

one

w

ould

susp

et

that

it

is

NP-hard

to

ompute.

T

urning

to

nite

rings,

w

e

an

try

to

use

W

edderburn's

deomp

o-

sition

theorem

for

semisimple

rings

to

dene

anonial

forms.

T

o

summarize,

w

e

ha

v

e

the

follo

wing

op

en-ended

question.

Problem

10.

What

ar

e

the

suitable

anoni

al

forms

for

nite

gr

oups

and

rings

and

what

is

omplexity

of

omputing

these

anoni

al

forms?

6

Ring

and

Group

Isomorphism

W

e

lo

ok

no

w

at

the

omplexit

y

of

isomorphism

testing

for

rings

and

groups.

These

questions

ha

v

e

ev

ok

ed

in

terest

due

to

the

reen

t

w

ork

b

y

Ka

y

al

and

Saxena

[21

℄

relating

the

omplexit

y

of

ring

isomorphism

to

b

oth

graph

iso-

morphism

and

in

teger

fatoring.

More

reen

tly

,

Agra

w

al

and

Saxena

in

a

fasinating

artile

[1℄

ha

v

e

highligh

ted

the

imp

ortane

of

nite

rings

and

their

automorphisms

for

omputational

problems

in

algebra

with

v

arious

ex-

amples.

W

e

disuss

the

main

results

ab

out

ring

isomorphism

and

automorphism

from

[21℄.

Alongside,

w

e

mak

e

some

new

observ

ations

for

the

group

isomor-

phism

problem

to

dra

w

omparisons

and

form

ulate

op

en

questions.

Reall

that

a

ring

(R ;

+;

:)

with

unit

y

is

a

omm

utativ

e

group

under

the

addition

op

eration

with

0

as

iden

tit

y

and

is

a

monoid

under

m

ultipliation

with

1

as

m

ultipliativ

e

iden

tit

y

,

together

with

m

ultipliation

distributing

o

v

er

addition.

The

omplexit

y

of

isomorphism

problems

migh

t

hange

dep

ending

on

the

w

a

y

the

input

instanes

are

represen

ted.

W

e

rst

onsider

the

represen

tation

of

a

nite

ring

R .

One

w

a

y

is

to

desrib

e

R

expliitly

b

y

its

addition

and

m

ultipliation

tables.

This

table

r

epr

esentation

is

of

size

O

(k

jR j

2

),

where

elemen

ts

of

R

are

eno

ded

as

strings

of

length

k

.

A

more

ompat

b

asis

r

epr

esentation

w

ould

b

e

to

desrib

e

R

b

y

giving

a

b

asis

for

R .

The

basis

is

an

indep

endent

generating

set

fe

1

;

e

2

;

;

e

m

g

for

the

additiv

e

group

(R ;

+).

Clearly

,

(R ;

+)

has

generating

sets

of

size

m

=

O

(log

jR j).

A

dditionally

,

to

desrib

e

the

m

ultipliativ

e

struture,

strutural

onstan

ts

of

the

ring

ij

k

2

Z;

1

i;

j;

k

m

are

giv

en,

where

e

i

e

j

=

P

k

ij

k

e

k

.

Sine

the

har

ateristi

of

R

is

b

ounded

b

y

jR j,

ea

h

strutural

onstan

t

is

m

bits

long.

No

w,

supp

ose

that

the

elemen

ts

of

R

are

eno

ded

as

strings

of

length

k

.

Clearly

the

en

tire

represen

tation

is

of

size

O

(k

m

4

).

Lik

ewise,

onsider

nite

groups

G

whose

elemen

ts

are

eno

ded

as

strings

of

length

k

.

W

e

ould

desrib

e

G

b

y

the

table

r

epr

esentation

b

y

giving

the

m

ultipliation

table

of

size

O

(k

jGj

2

).

Again,

a

more

ompat

represen

tation

for

nite

groups

w

ould

b

e

to

giv

e

a

generating

set

fg

1

;

g

2

;

;

g

k

g

for

G,

where

the

m

ultipliation

op

eration

is

impliitly

desrib

ed

b

y

a

bla

k-b

o

x

[13,

9℄.

The

bla

k-b

o

x

mo

del

in

tro

dued

b

y

[13,

9

℄

is

a

on

v

enien

t

setting

to

study

the

omplexit

y

of

group-theoreti

problems

that

do

not

tak

e

adv

an

tage

of

the

atual

group

op

eration

(p

erm

utation

groups

or

matrix

groups

et).

A

third

p

ossibilit

y

for

represen

ting

nite

ab

elian

groups

b

y

giving

inde-

p

endent

generating

sets.

Whether

an

arbitrary

generating

set

an

b

e

trans-

formed

to

an

indep

endent

generating

set

in

p

olynomial

time

is

op

en.

It

is

related

to

mem

b

ership

testing

and

the

disrete

log

problem.

Ho

w

ev

er,

this

transformation

an

b

e

done

b

y

a

p

olynomial

time

quan

tum

algorithm.

In-

deed,

isomorphism

testing

for

ab

elian

bla

k-b

o

x

groups

giv

en

b

y

generating

sets

an

b

e

done

in

quan

tum

p

olynomial

time

(see

[31

℄

for

example).

Problem

11.

What

is

the

omplexity

of

onverting

a

gener

ator

r

epr

esenta-

tion

to

a

b

asis

r

epr

esentation

for

nite

rings?

Notie

that

the

basis

represen

tation

for

nite

rings

is

more

strutured

than

the

generator

represen

tation

for

nite

groups.

The

nier

represen

tation

is

basially

due

to

the

fat

that

the

additiv

e

group

of

a

nite

ring

is

omm

u-

tativ

e.

Indeed,

if

a

nite

group

G

is

giv

en

b

y

a

generator

set

hg

1

;

g

2

;

;

g

k

i,

in

general

it

is

not

p

ossible

to

express

an

arbitrary

elemen

t

g

2

G

as

a

p

olynomial-size

pro

dut

Q

m

j

=1

g

i

j

!

Ho

w

ev

er

the

rea

habilit

y

lemma

of

[13

℄

sho

ws

that

it

is

p

ossible

to

express

g

as

a

p

olynomial-size

straigh

t-line

pro-

gram

o

v

er

the

generators.

In

this

setion

w

e

fo

us

on

the

basis

and

generator

represen

tation

for

rings

and

groups.

W

e

will

disuss

the

table

represen

tation

for

these

problems

in

Setion

7.

Ka

y

al

and

Saxena

[21℄

study

the

omplexit

y

of

ring

isomorphism.

W

e

reall

their

main

results

here.

F

or

rings

input

in

the

basis

represen

tation,

it

is

sho

wn

in

[21

℄

that

the

problems

of

nding

a

ring

automorphism,

ounting

ring

automorphisms,

ring

isomorphism

testing,

and

nding

a

ring

isomorphism

are

all

essen

tially

in

AM

\

oAM .

More

preisely

,

the

funtional

v

ersions

of

these

problems

are

in

FP

AM\oAM

.

Curiously

,

the

problem

deiding

if

a

ring

has

a

non

trivial

automorphism

is

in

P

[21℄.

This

is

essen

tially

b

eause

those

nite

rings

that

do

not

ha

v

e

non

trivial

automorphisms

ha

v

e

a

nie

mathematial

desription

whi

h

an

b

e

tested

in

p

olynomial

time.

In

[21℄

the

onnetion

b

et

w

een

ring

isomorphism

and

in

teger

fatoring

is

also

studied.

It

is

sho

wn

that

oun

ting

the

n

um

b

er

of

ring

automorphisms

is

harder

than

in

teger

fatoring

and

nding

a

non

trivial

automorphism

is

equiv

alen

t

to

in

teger

fatoring

(via

randomized

redutions).

It

is

in

teresting

to

ompare

these

results

with

the

situation

for

group

iso-

morphism.

A

basi

dierene

b

et

w

een

the

t

w

o

problems

is

in

the

desription

of

an

isomorphism.

A

ring

isomorphism

b

et

w

een

t

w

o

rings

R

1

and

R

2

in

basis

represen

tation

an

b

e

desrib

ed

b

y

an

in

v

ertible

in

teger

matrix

(after

suitably

mo

difying

the

bases

in

p

olynomial

time).

Ho

w

ev

er,

in

the

ase

of

an

isomorphism

'

b

et

w

een

t

w

o

nite

groups

G

and

H

giv

en

b

y

generator

sets,

there

seems

no

mathematially

expliit

w

a

y

to

desrib

e

a

group

isomorphism.

W

e

an

only

desrib

e

'

b

y

taking

ea

h

generator

g

i

of

G

and

expressing

'(g

i

)

as

a

straigh

t-line

program

o

v

er

the

generators

of

H

.

Nev

ertheless,

it

is

sho

wn

in

[9℄

that

bla

k-b

o

x

group

isomorphism

is

in

AM

\

oAM .

In

the

ase

of

p

erm

utation

group

isomorphism,

where

the

t

w

o

input

groups

are

p

erm

utation

groups

and

hene

more

amenable,

the

group

isomorphism

problem

is

sho

wn

to

b

e

in

NP

\

oAM .

Sine

the

isomorphisms

(or

automorphisms)

of

nite

groups

giv

en

b

y

gen-

erators

do

not

ha

v

e

expliit

mathematial

desriptions,

w

e

do

not

ha

v

e

an

FP

AM\oAM

b

ound

for

oun

ting

the

n

um

b

er

of

group

automorphisms

(equiv-

alen

tly

isomorphisms).

Ho

w

ev

er,

supp

ose

a

mapping

'

:

G

!

H

is

giv

en

b

y

'(g

i

)

as

a

straigh

t-line

program

o

v

er

the

generators

of

H

for

ea

h

generator

g

i

of

G.

Then

testing

if

'

denes

an

isomorphism

is

in

AM

\

oAM

due

to

the

order-v

eriation

in

terativ

e

proto

ol

of

Babai

[9℄.

Using

this

w

e

an

giv

e

a

#P

NP

upp

er

b

ound:

Supp

ose

elemen

ts

of

G

and

H

are

eno

ded

as

strings

of

length

m.

F

or

the

generators

g

1

;

g

2

;

;

g

k

,

the

#P

orale

ma

hine

guesses

the

images

'(g

i

);

1

i

k

as

strings

of

length

m.

Using

an

NP

orale,

it

then

omputes

the

straigh

t-line

programs

for

ea

h

'(g

i

),

o

v

er

the

generators

of

H

.

No

w,

a

new

group

K

is

formed,

that

is

generated

b

y

the

pairs

(g

i

;

'(g

i

)).

Notie

that

K

is

a

subgroup

of

G

H

.

The

order

v

eria-

tion

AM

proto

ol

of

[9℄

an

no

w

b

e

used

to

ompare

the

orders

of

G

and

K

and

to

aept

if

and

only

if

their

orders

are

equal.

Clearly

,

this

upp

er

b

ound

also

holds

for

the

omplexit

y

of

omputing

the

n

um

b

er

of

automorphisms

of

G.

Sine

#P

9:AM

=

#P

AM

=

#P

NP

w

e

ha

v

e

the

follo

wing:

Prop

osition

5.

Computing

the

numb

er

of

isomorphism

b

etwe

en

two

gr

oups

G

and

H

given

by

gener

ating

sets

is

in

#P

NP

.

Problem

12.

Tightly

lassify

the

omplexity

of

omputing

the

numb

er

of

gr

oup

isomorphisms,

when

the

gr

oups

ar

e

in

the

gener

ator

r

epr

esentation.

Mor

e

pr

e

isely,

for

a

nite

gr

oup

G

given

by

gener

ators

in

the

blak-b

ox

mo

del,

is

the

pr

oblem

of

omputing

the

numb

er

of

automorphism

in

G

low

for

any

level

of

PH?

In

on

trast

note

that

oun

ting

ring

automorphisms

is

lo

w

for

AM

\

oAM .

Ho

w

ev

er

hardness

questions

remain.

Problem

13.

Is

ounting

ring

automorphisms

har

der

than

disr

ete

lo

g?

Is

ring

isomorphism

(de

ision

or

se

ar

h

version)

har

der

than

disr

ete

lo

g?

W

e

next

onsider

the

question

of

rigidity.

Rigid

nite

groups

are

nite

groups

with

no

non

trivial

automorphism.

W

e

note

that

the

algorithmi

prob-

lem

is

trivial

here.

Prop

osition

6.

Ther

e

ar

e

no

rigid

gr

oups

ex

ept

gr

oups

of

or

der

1

and

2.

Pro

of.

Clearly

the

groups

of

order

1

and

2

are

rigid.

Let

G

b

e

a

nite

group

of

size

more

than

2.

If

G

is

nonab

elian

then

let

g

2

G

su

h

that

g

do

es

not

omm

ute

with

all

elemen

ts

of

G.

Then

the

inner

automorphism

g

dened

as:

g

:

x

7!

g

xg

1

is

learly

a

non

trivial

automorphism.

On

the

other

hand

if

G

is

ab

elian,

then

w

e

use

the

struture

theorem

of

ab

elian

groups

to

deomp

ose

G

as

a

diret

pro

dut

of

yli

groups

G

1

G

2

G

r

.

Supp

ose

jG

i

j

=

t

>

2

for

one

of

the

yli

groups

G

i

.

Let

a

2

G

i

b

e

a

generator.

Then

a

k

is

also

a

generator

of

G

i

for

ea

h

k

su

h

that

gd(k

;

t)

=

1.

It

is

easy

to

see

that

a

7!

a

k

is

an

automorphism

of

G

i

if

and

only

if

gd(k

;

t)

=

1.

If

t

>

2

there

is

at

least

one

su

h

k

>

1

so

that

a

7!

a

k

is

a

non

trivial

automorphism

of

G

i

.

This

an

b

e

extended

easily

to

a

non

trivial

automorphism

of

G.

On

the

other

hand,

if

jG

i

j

=

2

for

ea

h

i,

then

G

is

a

v

etor

spae

o

v

er

F

2

of

dimension

r

.

Hene

an

y

nonsingular

r

r

matrix

dieren

t

from

iden

tit

y

o

v

er

F

2

is

a

non

trivial

automorphism

of

G.

It

is

sho

wn

in

[21℄

that

all

rigid

rings

ha

v

e

a

simple

struture

that

an

b

e

easily

reognized.

The

ab

o

v

e

prop

osition

implies

that

group

rigidit

y

is

ev

en

easier

to

test

than

testing

rigidit

y

of

rings.

W

e

reall

that

the

rigidit

y

question

for

graphs

is

not

kno

wn

to

b

e

in

P

.

W

e

no

w

sho

w

that

omputing

the

n

um

b

er

of

group

automorphisms

is

also

harder

than

in

teger

fatoring

(analogous

to

the

result

for

ring

automorphisms

in

[21℄).

In

the

ase

of

group

automorphisms

the

hardness

is

easy

to

sho

w.

Consider

(Z

n

;

+),

the

additiv

e

group

of

in

tegers

mo

dulo

n.

The

group

is

yli

with

1

as

generator,

and

1

7!

j

denes

an

automorphism

if

and

only

if

gd (j;

n)

=

1,

sine

j

2

Z

n

is

a

generator

i

it

is

relativ

ely

prime

to

n.

Th

us,

(Z

n

;

+)

has

preisely

'(n)

generators,

where

'

is

the

Euler

'-funtion.

It

fol-

lo

ws

that

omputing

#Aut(Z

n

)

implied

omputing

'(n)

whi

h

is

equiv

alen

t

to

in

teger

fatoring

w.r.t.

randomized

p

olynomial-time

redutions.

Prop

osition

7.

Inte

ger

fatoring

is

r

e

duible

to

omputing

the

numb

er

of

automorphism

for

a

nite

gr

oup

G

given

by

gener

ators.

It

w

ould

b

e

in

teresting

to

kno

w

if

the

same

result

holds

for

p

erm

utation

groups.

Problem

14.

Is

inte

ger

fatoring

r

e

duible

to

omputing

the

numb

er

of

au-

tomorphism

of

a

p

ermutation

gr

oup

G

S

n

given

by

gener

ators?

In

[21℄

it

is

sho

wn

that

nding

a

non

trivial

ring

automorphism

is

equiv-

alen

t

to

in

teger

fatoring.

In

terestingly

,

for

the

ase

of

groups

the

situation

is

quite

dieren

t.

Let

G

b

e

a

group

giv

en

b

y

generators.

W

e

an

he

k

if

it

is

nonab

elian

(simply

b

y

he

king

if

the

generators

omm

ute

with

ea

h

other).

If

G

is

nonab

elian,

w

e

will

nd

a

generator

g

su

h

that

g

g

i

6=

g

i

g

for

some

other

generator

g

i

of

G.

Clearly

,

the

inner

automorphism

g

dened

b

y

g

:

x

7!

g

xg

1

is

a

non

trivial

automorphism.

Prop

osition

8.

Ther

e

is

a

p

olynomial-time

algorithm

for

nding

a

nontrivial

automorphism

of

a

nonab

elian

gr

oup

given

by

gener

ator

set.

Ab

elian

groups

dot

ha

v

e

inner

automorphisms.

On

the

other

hand

if

G

is

an

ab

elian

group

giv

en

b

y

an

indep

endent

generating

set

hg

1

;

g

2

;

;

g

k

i,

and

a

m

ultiple

n

of

jGj

is

kno

wn,

then

it

is

easy

to

nd

a

non

trivial

automor-

phism

applying

the

ideas

of

Prop

osition

6.

If

ea

h

g

i

has

order

2

then

G

is

v

etor

spae

o

v

er

F

2

and

an

y

nonsingular

k

k

matrix

is

an

automorphism.

Otherwise,

if

g

i

has

order

more

than

2

then

pi

k

a

p

ositiv

e

in

teger

a

>

1

su

h

that

gd(a;

n)

=

1

b

y

randomly

pi

king

a

2

[n

1℄.

Then,

with

high

probabilit

y

g

i

6=

g

a

i

and

g

i

and

g

a

i

ha

v

e

the

same

order.

No

w,

g

i

7!

g

a

i

and

g

j

7!

g

j

;

j

6=

i

denes

a

non

trivial

automorphism.

Ho

w

ev

er,

if

an

ab

elian

group

G

is

giv

en

b

y

a

generating

set

(not

nees-

sarily

indep

enden

t)

then

the

omplexit

y

of

the

problem

is

op

en.

Problem

15.

F

or

ab

elian

gr

oups,

is

the

pr

oblem

of

nding

a

nontrivial

au-

tomorphism

har

der

than

inte

ger

fatoring?

Is

it

har

der

than

disr

ete

lo

g?

Another

observ

ation

is

that

the

problem

of

group

isomorphism

testing

is

harder

than

the

deision

v

ersion

of

disrete

log:

giv

en

a;

b

2

Z

n

,

the

problem

is

to

he

k

if

a

is

in

the

yli

group

generated

b

y

b

(i.e.

a

2

hbi).

Clearly

,

a

2

hbi

i

ha;

bi

is

isomorphi

to

hbi.

More

generally

,

the

mem

b

ership

testing

problem

for

groups

redues

to

group

isomorphism.

F

or

b

oth

ring

and

group

isomorphism

the

relativ

e

omplexities

of

sear

h

and

deision

remains

op

en.

In

the

ase

of

graph

isomorphism,

sear

h

is

p

olynomial-time

reduible

to

deision.

The

redution

uses

graph

gadgets

to

guide

a

prex

sear

h.

It

is

not

lear

ho

w

to

build

similar

gadgets

for

groups

and

rings.

Problem

16.

Is

se

ar

h

p

olynomial-time

r

e

duible

to

de

ision

for

gr

oup

iso-

morphism

and

ring

isomorphism?

7

Derandomization

Babai

lassied

in

[7

℄

the

graph

non-isomorphism

problem

in

AM,

a

ran-

domized

v

ersion

of

NP

that

an

b

e

desrib

ed

in

terms

of

Arth

ur

Merlin

proto

ols.

Sev

eral

authors

(e.g.

[3,

22

,

30

℄)

ha

v

e

studied

derandomization

of

AM

to

NP

under

suitable

hardness

assumptions,

th

us

sho

wing

that

GI

b

elongs

to

NP

\

oNP .

This

derandomization

w

orks

for

the

en

tire

lass

AM.

It

is

natural

to

ask

if

the

AM

proto

ol

for

graph

non-isomorphism

an

b

e

unonditionally

derandomized.

Problem

17.

Can

the

AM

pr

oto

ol

for

gr

aph

non-isomorphism

b

e

der

an-

domize

d

un

onditional

ly?

Or

under

we

aker

har

dness

assumptions

that

those

use

d

in

[3

,

22,

30℄?

W

e

onsidered

in

[6℄

the

question

of

whether

the

group

isomorphism

prob-

lem

(for

the

ase

of

groups

giv

en

b

y

m

ultipliation

tables)

lies

in

NP

\

oNP

.

This

migh

t

b

e

easier

to

sho

w

than

for

the

ase

of

GI

sine

group

isomorphism

in

the

table

r

epr

esentation

app

ears

to

b

e

an

easier

problem.

F

ollo

wing

the

same

approa

h

as

it

has

b

een

done

for

the

ase

of

GI

w

e

sho

w

ed

that

group

non-isomorphism

has

an

Arth

ur-Merlin

proto

ol

with

the

prop

ert

y

that

on

input

groups

of

size

n,

Arth

ur

uses

O

(log

6

n)

random

bits

and

Merlin

uses

only

O

(log

2

n)

nondeterministi

bits.

F

or

the

ase

of

solv

able

groups

w

e

ould

derandomize

this

restrited

proto

ol

applying

t

w

o

dieren

t

metho

ds

sho

wing

that:

there

is

a

nondeterministi

p

olynomial

time

algorithm

for

the

group

non-isomorphism

problem

restrited

to

solv

able

groups

that

is

inorret

for

at

most

2

log

O

(1)

n

inputs

of

length

n,

and

under

the

assumption

EXP

6

ioPSP

A

CE

1

the

group

isomorphism

prob-

lem

restrited

to

solv

able

groups

is

in

NP

\

oNP

.

The

restrition

to

solv

able

groups

omes

from

the

fat

that

for

the

de-

randomization,

an

easy

to

ompute

suint

represen

tation

for

the

groups

is

needed.

This

exists

for

the

ase

of

solv

able

groups,

but

it

is

an

op

en

question

whether

it

exists

for

general

groups

(related

to

a

form

of

the

short

presen

tation

onjeture

kno

wn

to

b

e

true

for

almost

all

nite

simple

groups).

Problem

18.

Do

the

ab

ove

der

andomization

r

esults

hold

for

the

ase

of

gener

al

gr

oups?

As

men

tioned

in

[6℄

the

derandomization

do

es

w

ork

for

general

groups

assuming

the

short

presen

tation

onjeture.

T

urning

to

ring

isomorphism

in

the

table

represen

tation

the

ab

o

v

e

prob-

lem

is

easy

to

resolv

e.

As

the

additiv

e

group

is

ab

elian,

rings

ha

v

e

suint

represen

tations

of

the

appropriate

t

yp

e

of

p

olylogarithmi

size

in

the

n

um

b

er

of

ring

elemen

ts.

Therefore

Problem

18

an

b

e

answ

ered

armativ

ely

for

the

ase

of

rings

with

addition

and

m

ultipliation

tables

giv

en

expliitly

.

Th

us,

one

w

ould

exp

et

that

the

follo

wing

problem

is

easier

than

for

groups.

F

or

rings

giv

en

in

this

w

a

y

w

e

an

ask

the

general

question.

Problem

19.

Is

the

ring

isomorphism

pr

oblem

in

the

table

r

epr

esentation

in

NP

\

oNP?

1

A

language

L

is

in

ioPSP

A

CE

if

there

is

a

PSP

A

CE

ma

hine

that

is

orret

on

L

for

innitely

man

y

input

lengths.

8

Quan

tum

Computing

In

this

setion

w

e

desrib

e

the

attempts

at

a

quan

tum

algorithmi

solution

to

the

graph

isomorphism

problem

and

the

diulties

in

this

approa

h.

The

generi

problem

that

underlies

the

disrete

log

problem,

in

teger

fatoring

and

graph

isomorphism

is

the

hidden

subgroup

problem.

W

e

explain

the

hidden

subgroup

problem

and

summarize

the

progress

made

on

it.

Then

w

e

disuss

some

in

teresting

onnetions

b

et

w

een

quan

tum

p

olynomial

time

and

oun

ting

omplexit

y

lasses.

First,

w

e

reall

the

denition

of

the

hidden

subgroup

problem.

Denition

9.

The

input

instan

e

of

the

hidden

subgroup

problem

HSP

is

a

nite

gr

oup

G

given

by

a

gener

ator

set.

A

dditional

ly,

a

funtion

f

fr

om

G

to

some

nite

set

X

is

given

as

an

or

ale,

suh

that

f

is

onstant

and

distint

on

dier

ent

right

osets

of

some

sub

gr

oup

H

of

G.

The

pr

oblem

is

to

determine

a

gener

ator

set

for

H

.

The

hidden

subgroup

problem

is

a

generi

problem

whi

h

aptures

sev

eral

questions.

W

e

explain

ho

w

it

aptures

graph

isomorphism.

Let

X

b

e

a

nite

graph.

No

w,

letting

G

b

e

the

p

erm

utation

group

S

n

w

e

dene

the

hiding

funtion

f

:

S

n

!

G

n

as

f

(

)

=

X

,

where

X

is

the

graph

obtained

from

X

b

y

p

erm

uting

its

v

erties

with

the

p

erm

utation

.

It

is

easy

to

see

that

the

hidden

subgroup

is

the

automorphism

group

Aut(X)

of

X

.

Determining

the

automorphism

group

of

a

graph

is

p

olynomial-time

equiv

alen

t

to

graph

isomorphism.

Shor's

quan

tum

algorithms

for

in

teger

fatoring

and

disrete

log

are

es-

sen

tially

solutions

of

suitable

HSP's

where

the

group

G

is

ab

elian.

Indeed,

Shor's

te

hnique

[33

℄

yields

a

p

olynomial-time

quan

tum

algorithm

for

HSP

when

G

is

ab

elian

(see

e.g.

[31

℄).

Ho

w

ev

er,

the

status

of

HSP

is

op

en

for

gen-

eral

nonab

elian

groups,

exept

for

some

sp

eial

ases

(see,

e.g.

[18

,

19,

32

℄).

In

partiular,

for

G

=

S

n

,

it

is

not

kno

wn

if

HSP

has

quan

tum

p

olynomial

time

algorithms.

F

or

ring

isomorphism

(in

the

basis

represen

tation)

it

is

easy

to

form

ulate

the

problem

of

omputing

the

automorphism

group

of

a

omm

utativ

e

ring

of

harateristi

d

as

a

hidden

subgroup

problem,

where

the

group

G

w

ould

b

e

the

nite

group

onsisting

of

matries

of

a

suitable

dimension

in

v

ertible

mo

dulo

d.

Again,

su

h

a

matrix

group

is

nonab

elian

in

general

(it

ev

en

on

tains

S

n

)

whi

h

mak

es

the

orresp

onding

HSP

a

hard

problem.

The

hidden

subgroup

approa

h

to

designing

an

eien

t

quan

tum

algo-

rithm

for

graph

isomorphism

seems

to

ha

v

e

limitations:

v

ery

little

progress

has

b

een

made

on

the

nonab

elian

hidden

subgroup

problem.

It

app

ears

that

some

new

quan

tum

algorithmi

te

hniques

are

required.

But

there

migh

t

b

e

restrited

glaph

lasses

of

for

whi

h

it

is

p

osible

to

test

isomorphism

in

quan

tum

p

olynomial

time

with

the

presen

t

te

hniques.

Problem

20.

Is

ther

e

a

r

estrite

d

lass

of

gr

aphs

for

whih

the

isomorphism

pr

oblem

(not

known

to

b

e

in

P)

has

p

olynomial

time

quantum

algorithms?

GI

has

another

onnetion

with

the

lass

BQP

of

problems

omputable

in

quan

tum

p

olynomial

time.

F

ortno

w

and

Rogers

[17

℄

ha

v

e

sho

wn

that

BQP

is

lo

w

for

PP

,

i.e.

an

y

problem

is

BQP

is

is

p

o

w

erless

as

orale

for

PP

.

This

is

in

fat

the

b

est

kno

wn

upp

er

b

ound

for

BQP

in

terms

of

omplexit

y

lasses.

In

[23℄

it

is

sho

wn

that

graph

isomorphism

and

sev

eral

other

p

erm

utation

group

problems

are

also

lo

w

for

PP

.

This

w

as

strengthened

in

[4℄

where

it

is

sho

wn

that

the

hidden

subgroup

problem

for

p

erm

utation

groups

(and

hene

graph

isomorphism)

is

in

a

more

restrited

oun

ting

omplexit

y

lass.

Ho

w

ev

er,

similar

questions

are

op

en

for

ring

and

(nonab

elian)

group

isomorphism.

Problem

21.

Is

the

ring

isomorphism

pr

oblem

low

for

PP?

Is

the

gr

oup

isomorphism

pr

oblem

for

nonab

elian

gr

oups

low

for

PP ?

Referenes

[1℄

M.

Agra

w

al

and

N.

Saxena.

Automorphisms

of

Finite

Rings

and

Appliations

to

Complexit

y

of

Problems.

Pr

o

.

Symp.

The

or

eti

al

Asp

e

ts

of

Computer

Sien

e,

LNCS

3404,

1-17,

Springer

V

erlag,

F

eb

2005.

[2℄

E.

Allender.

Arithmeti

Ciruits

and

Coun

ting

Complexit

y

Classes.

Quaderni

di

Matemati

a

series,

Edited

b

y

Jan

Kra

jiek,

2004.

[3℄

V.

Arvind

and

J.

K

öbler,

On

resoure

b

ounded

measure

and

pseudorandom-

ness,

Pro

.

17th

FSTT

Conferene

Leture

Notes

in

Computer

Siene

1346

Springer

V

erlag,

235249,

(1997).

[4℄

V.

Arvind

and

P

.

P

.

Kurur.

Graph

Isomorphism

is

in

SPP.

Pr

o

.

F

oundations

of

Computer

Sien

e,

743-750,

2002.

[5℄

V.

Arvind,

P

.

P

.

Kurur,

and

T.C.

Vija

y

aragha

v

an.

Bounded

olor

m

ultipli-

it

y

graph

isomorphism

is

in

the

#L

Hierar

h

y

.

In

Pr

o

e

e

dings

of

the

20th

Confer

en

e

on

Computational

Complexity,

2005,

to

app

ear.

[6℄

V.

Arvind

and

J.

T

orán.

Solv

able

group

isomorphism

is

almost

in

NP

\

oNP.

Pr

o

.

19th

IEEE

Confer

en

e

on

Computational

Complexity,

91-103,

2004.

[7℄

L.

Babai.

T

rading

group

theory

for

randomness.

Pro

.

17th

A

CM

Symp

osium

on

Theory

of

Computing,

421429,

1985.

[8℄

L.

Babai.

A

Las

V

egas-NC

Algorithm

for

isomorphism

of

graphs

with

b

ounded

m

ultipliit

y

of

eigen

v

alues.

Pr

o

.

F

oundations

of

Computer

Sien

e,

303-312,

1986.

[9℄

L.

Babai.

Bounded

round

in

terativ

e

pro

ofs

in

nite

groups.

SIAM

journal

of

Disr

ete

Mathematis,

5(1):88111,

F

ebruary

1992.

[10℄

L.

Babai

and

E.

M.

Luks.

Canonial

lab

eling

of

graphs.

In

Pr

o

e

e

dings

of

the

Fifte

enth

A

nnual

A

CM

Symp

osium

on

The

ory

of

Computing,

pages

171183,

1983.

[11℄

L.

Babai,

E.

M.

Luks,

and

Á.

Seress.

P

erm

utation

Groups

in

NC.

Pr

o

e

e

dings

Symp.

The

ory

of

Computing,

409-420,

1987.

[12℄

L.

Babai

and

S.

Moran.

Arth

ur-Merlin

games:

a

randomized

pro

of

system,

and

a

hierar

h

y

of

omplexit

y

lasses.

Journal

of

Computer

and

System

Sien

es,

36:254276,

1988.

[13℄

L.

Babai

and

E.

Szemeredi.

On

the

omplexit

y

of

matrix

group

problems

I.

In

Pr

o

e

e

dings

of

the

24

th

IEEE

F

oundations

of

Computer

Sien

e,

pages

229240,

1984.

[14℄

J.

Balázar,

J.

Díaz,

and

J.

Gabarró.

Strutur

al

Complexity

I

&

II.

ET

A

CS

monographs

on

theoretial

omputer

siene.

Springer-V

erlag,

Berlin,

1988

and

1990.

[15℄

R.

Boppana,

J.

Hastad,

and

S.

Za

hos.

Do

es

o-NP

ha

v

e

short

in

terativ

e

pro

ofs.

Information

Pr

o

essing

L

etters,

25:127132,

Ma

y

1987.

[16℄

S.

A.

Co

ok.

A

taxonom

y

of

problems

with

fast

parallel

algorithms.

Information

and

Contr

ol,

64(1):222,

1985.

[17℄

L.

F

ortno

w

and

J.

D.

Rogers.

Complexit

y

limitations

on

quan

tum

ompu-

tation.

In

IEEE

Confer

en

e

on

Computational

Complexity,

pages

202209,

1998.

[18℄

S

Hallgren,

A

Russel,

and

A

T

a-Shma.

Normal

subgroup

reonstrution

and

quan

tum

omputing

using

group

represen

tation.

In

Pr

o

e

e

dings

of

the

32

nd

A

CM

Symp

osium

on

The

ory

of

Computing,

pages

627635,

P

ortland,

Oregon,

21-23

Ma

y

2000.

[19℄

G.

Iv

an

y

os,

F.

Magniez,

and

M.

San

tha.

Eien

t

quan

tum

algorithms

for

some

instanes

of

the

non-ab

elian

hidden

subgroup

problem.

In

13

th

A

CM

Symp

osium

on

Par

al

lel

A

lgorithms

and

A

r

hite

tur

es,

pages

263270,

2001.

[20℄

B.

Jenner,

J.

K

öbler,

P

.

MKenzie,

J.

T

orán.

Completeness

results

for

graph

isomorphism.

J.

Comput.

Syst.

Sien

es,

66(3):

549-566,

2003.

[21℄

N.

Ka

y

al

and

N.

Saxena.

On

ring

isomorphism

and

automorphism

problems.

In

Pr

o

.

20th

IEEE

Confer

en

e

on

Computational

Complexity,

June

2005,

to

app

ear.

[22℄

A.

Kliv

ans

and

D.

v

an

Melk

eb

eek,

Graph

Isomorphism

has

sub

exp

onen

tial

size

pro

v

ers

unless

the

p

olynomial

time

hierar

h

y

ollapses.

In

Pro

.

31st

A

CM

STOC,

1999,

659667.

[23℄

J.

Köbler,

U.

S

höning,

and

J.

T

orán.

Graph

isomorphism

is

lo

w

for

PP.

Computational

Complexity,

2(4):301330,

1992.

[24℄

Johannes

Köbler,

Uw

e

S

höning,

and

Jaob

o

T

orán.

The

Gr

aph

Isomorphism

Pr

oblem:

Its

Strutur

al

Complexity.

Birkhauser,

1993.

[25℄

E.

M.

Luks.

Isomorphism

of

Graphs

of

Bounded

V

alene

an

b

e

T

ested

in

P

olynomial

Time.

Journal

of

Computer

and

System

Sien

es,

25(1):

42-65,

1982.

[26℄

E.

M.

Luks.

P

arallel

algorithms

for

p

erm

utation

groups

and

graph

isomor-

phism.

In

Pr

o

e

e

dings

of

the

IEEE

F

oundations

of

Computer

Sien

e,

IEEE

Computer

So

iet

y

,

292-302,

1986.

[27℄

E.

M.

Luks.

P

erm

utation

groups

and

p

olynomial

time

omputations.

DIMA

CS

Series

in

Disr

ete

Mathematis

and

The

or

eti

al

Computer

Sien

e,

11:139

175,

1993.

[28℄

R.

Mathon.

A

note

on

the

graph

isomorphism

oun

ting

problem.

Information

Pr

o

essing

L

etters,

8:131132,

1979.

[29℄

G.

L.

Miller.

Isomorphism

of

k-Con

tratible

Graphs.

A

Generalization

of

Bounded

V

alene

and

Bounded

Gen

us.

Information

and

Contr

ol,

56(1/2):

1-20,

1983.

[30℄

P

.B.

Miltersen

and

N.

Vino

d

handran,

Derandomizing

Arth

ur-Merlin

games

using

hitting

sets,

in

Pro

.

40th

IEEE

Symp

osium

on

F

oundations

of

Com-

puter

Siene,

1999,

7180.

[31℄

M.

Mosa.

Quantum

Computer

algorithms.

PhD

thesis,

Oxford

Univ

ersit

y

,

1999.

[32℄

M.

Rötteler

and

T.

Beth,

P

olynomial-Time

Solution

to

the

Hidden

Subgroup

Problem

for

a

Class

of

non-ab

elian

Groups.

ArXiv

preprin

t

quan

t-ph/9812070,

1998.

[33℄

P

.

Shor.

P

olynomial-time

algorithms

for

prime

fatorization

and

disrete

log-

arithms

on

a

quan

tum

omputer.

SIAM

Journal

on

Computing,

26(5):1484

1509,

1997.

[34℄

U.

S

höning.

Graph

isomorphism

is

in

the

lo

w

hierar

h

y

.

Journal

of

Computer

and

System

Sien

es,

37:312323,

1988.

[35℄

J.

T

orán.

On

the

hardness

of

graph

isomorphism,

SIAM

J.

Comput.

33(5):

10931108,

2004.