Classes de Problemas e Complexidade de Tempo
Classificado em Computação
Escrito em em 
português com um tamanho de 3,99 KB.
Comp:
Todo problema possível de ser computável por uma MT. Um problema computável não se tem garantia sobre sua decidibilidade e sua complexidade de tempo.Dec:
São todos os problemas decidíveis por uma MT, independente da complexidade de tempo.Trat:
Um problema é dito tratável se decidível por uma MT em tempo polinomial em relação a entrada.Trat. Teórica:
Envolve os problemas tratáveis tanto por uma MTD quanto por MTND.Trat. Pratica:
Envolve apenas os problemas tratáveis por uma MTD.2. logn, sqrt(n), n/2, n, nlogn, n^2logn, n^3, 2^n, n!
3. O(n) + O(n2/3) + O(n) = O(n2)
4. V, F, V, F, V, V, F, F, V, F
Classe P:
Classe de problemas decidíveis em tempo polinomial em relação a entrada por uma MTD.Classe co-P:
Classe de problemas que são o complemento dos problemas de P. A classe co-P possui a mesma complexidade de tempo de P.
Classe NP:
Classe de problemas decidíveis em tempo polinomial em relação ao tamanho da entrada por uma MTND.
Classe NP-Completo:
Classe que contém os problemas mais difíceis em NP. Dado um problema pertencente a NP, se for possível reduzir polinomialmente um problema reconhecidamente NP-Completo a pi, então o pi é NP-Completo.
Classe co-NP:
Classe de problemas que contém os complementos dos problemas NP.
Exp:
Classe de problemas decidíveis em tempo exponencial em relação ao tamanho da entrada por uma MTND.
NP-Hard:
Classe que contém os problemas mais difíceis em NP-Completo. Contém os problemas NP-Completo que são realizáveis polinomialmente de um problema NP-Hard.
a) P=co-P:
O complemento de um problema P e o problema P em si possuem a mesma complexidade de tempo. Um algoritmo em tempo polinomial decide sobre um problema P e seu complemento.
b) P ⊆ NP:
Implica que a classe P está contida em NP. A classe P é um caso particular da classe NP que não possui não determinismo, todas as transições de uma máquina que implementa uma linguagem da classe P têm transições bem definidas.
c) NP≠co-NP:
Implica que o complemento de NP não é decidível na mesma complexidade de tempo de NP. Determinar se o complemento de NP é um problema mais difícil que NP é preciso testar todos os passos de computação não determinístico para garantir a não-completude.
a. Seja M uma MTD L={w|M aceita w sse sendo w o conjunto de cláusulas e variáveis lógicas e c um certificado válido contendo os valores verdade de cada variável lógica.
w,c ∈ ∑={(,), , , 0, 1, V, ^, ⌐ , V, F}*}
Codifique cada uma das n variáveis lógicas com uma representação em binário. Em w coloque cada cláusula com suas variáveis já codificadas em c, armazene o certificado, com cada variável codificada em binário, seguido do seu valor verdade separado por vírgula.
b. A fita 1 armazena a entrada w/A a fita 2 armazena a entrada c / A a fita 3 armazena as cláusulas com suas variáveis substituídas pelo seu valor verdade.
Func.:
Para cada uma das cláusulas, pegue cada valor-verdade na fita 2 de cada variável lógica e construa a cláusula na fita 3 com os valores verdade substituindo a variável. Se um símbolo ⌙ preceder uma variável, inverta seu valor na fita 3. Na fita 1, marque cada variável que já foi substituída.
Quando todas as cláusulas tiverem sido substituídas, faça uma varredura na fita 3, se todos os valores verdade de alguma cláusula forem F, pare e rejeite. Caso contrário, aceite.
W=(1 V ⌙ 10 V 11)^(10 V ⌙ 11 V 100) / C= 1V, 10F, 11F, 100V