Lista 2 - exercício 4

Lista 2 - exercício 4

por Andre Jucovsky Bianchi -
Número de respostas: 2
No exercício 4, a linguagem que se quer mostrar que está em P é:

POT-PERM = { <p, q, t> : p = qt onde p e q são permutações sobre { 1, . . . , k } e t é um inteiro em binário }

Do jeito que foi definido, dá a impressão que o k é o mesmo para p e q, mas eu só consigo entender se na verdade p for uma permutação sobre { 1, . . . , kp } e q for uma permutação sobre { 1, . . . , kq }, com kp = t . kq.

Procede ou eu que ainda não entendi o exercício?
Em resposta à Andre Jucovsky Bianchi

Re: Lista 2 - exercício 4

por César Machado -
Pelo que eu entendi, k é fixo,

q^t é aplicar a permutação t vezes.

Ex:

q: 35421

ou seja, q(1) = 3, q(2) = 5, q(3) = 4, etc.

q^2(1) = q(3) = 4
q^2(2) = q(5) = 1
...

e portanto q.q, ou q^2 = 41253