Problema de otimização combinatória

Professor Pedro M.

Identidade verificada

• CPF verificado
• E-mail verificado

Respondeu há 5 anos

Olá, Rúbia!
Para resolvermos esse problema podemos usar o fato de que P esta contido em NP intersecção co-NP. Assim se provarmos que pode ser encontrada uma solução para o problema com uma complexidade polinomial o exercício esta resolvido.
Portanto precisamos encontrar indices i1, ..., i n/2 tais que s_ij/ s_ij-1 = s_ij+1 / s_ij para j=2, ..., n/2 - 1. Seja i2 = k, para algum k em {1,2,3,...,n}, temos que
(s_i2)^2 = s_i1.s_i3
precisamos checar a lista de S, testando cada valor, para descobrirmos se existem i1, i3 em {1,2,3,...,n} que satisfazem a igualdade. A complexidade dessa tarefa será n^2, a mesma de um Selection Sort. Depos repetir o mesmo processo para i3 no lugar de i2, e assim por diante, fazendo a complexidade ser n^3 já que precisariamos repetir o processo de complexidade n^2 n/2 - 2 vezes.
Porém isso não resolve o problema, precisamos repetir o processo para i2 = k para todo valor de k em {1,2,3,...,n}, até testarmos todos (e não encontrarmos solução) ou então encontrarmos uma lista de indices i1, ..., i n/2 que solucione o problema. Então a complexidade total será n^4 no pior caso, e n no melhor (todas nossas primeiras escolhas de ij satisfazem a igualdade), ou seja, o problema esta em P, e consequentemente em NP intersecção co-NP.