Discussion between Isla_Bonita and Mariano Suárez-Álvarez

Feeds

08:52

Q: Is this Isomorphism in Polynomial Time?

Let $V=\{1,2,\cdots, n\}$ and $\Sigma = \{1,2,\cdots,k\}$ is a set of $k$ colours. Let $f, f' : V \mapsto \Sigma$ be two colouring of $V$. Isomorphism Problem : Given : $(V,f)$ and $(V,f')$ To Compute : $H = $ ISO$((V,f),(V,f'))$ (set of bijections from $V\mapsto V$ that preserve colour) (I ...

Mariano Suárez-Álvarez

Please explain the notation, at least. What is "$ISO((V,f),(V,f'))$"?

Isla_Bonita

@ Mariano Suárez-Álvarez I have edited the question

@Crostul It is a decision problem

Mariano Suárez-Álvarez

But $H$ has exponentially many elements in general (take, for example, $f$ and $f'$ constant with the same value) and therefore its elements cannot be listed in polynomial time.

Isla_Bonita

@ Crostul then print " no"

@ Mariano Suárez-Álvarez It is a decision problem (yes or no)

Mariano Suárez-Álvarez

What does it mean "to decide $H$"?

Isla_Bonita

08:52

@ Mariano Suárez-Álvarez Is H empty ?

Mariano Suárez-Álvarez

So what you want is "to decide if $H$ is empty or not".

Isla_Bonita

Yes Let me edit the question

Mariano Suárez-Álvarez

There is a very simple algorithm to decide emptiness: just count how many times each color appears in each coloring — if the counts are the same, then yes, if not, no. This is somewhat trivial.

Isla_Bonita

I need the generating set of $H$

which is polynomial

Crostul

Using brute force:

`for c in colours:
a=0
b=0
for v in vertices:
if f(v)=c:
a=a+1
if f'(v)=c:
b=b+1
if a=/b:
return "no"
return "yes"`

This has polynomial time.

sorry I couldn't make indentations in chat

for c in colours:
a=0
b=0
for v in vertices:
if f(v)=c:
a=a+1
end if
if f'(v)=c:
b=b+1
end if
end for
if a=/b:
return "no"
end if
end for
return "yes"

Isla_Bonita

09:09

Please explain in English statements what are u doin

a=/b means ?

last day (14 days later) »

all rooms