Número: 060
Enunciado:
Qual dos problemas abaixo NÃO é NP-difícil?
- Inferência de Haplótipos por Pura Parcimonia
- Inferência de Haplótipos por Resolução Máxima
- Inferência de Haplótipos por Filogenia Perfeita
- Programação Linear Inteira
- NDA
quinta-feira, 10 de fevereiro de 2011
060-2008
MO640 - Questão para a prova oral
Número: 060
Enunciado:
Qual dos problemas abaixo NÃO é NP-difícil?
Número: 060
Enunciado:
Qual dos problemas abaixo NÃO é NP-difícil?
Assinar:
Postar comentários (Atom)
Em teoria de Complexidade Computacional, NP é acrônimo em inglês de Tempo polinomial não determinístico (Non-Deterministic Polynomial time), que da nome a um conjunto de problemas de são resolvidos em tempo polinomial por uma Máquina de Turing não-determinística. Um exemplo é um grafo orientado G=(VE) onde se pretende encontrar o caminho simples mais longo entre dois vértices. A complexidade torna-se NP. Por outro lado, para um algoritmo que recebe entradas de tamanho n e seu tempo de execução no pior caso é O(n^k), onde k é uma constante qualquer, não é um problema NP.
ResponderExcluirRecebe o nome de NP-completo o subconjunto dos problemas de decisão NP de tal modo que se pode reduzir, todo problema NP, com uma redução de tempo polinomial, a um problema NP-completo.
NP-difícil é uma classe de problemas tão difícil quanto os problemas mais complexos em NP. Um problema H é NP-difícil se, e somente se, existe um problema NP-completo L que é redutível em tempo polinomial por uma máquina de Turing. L então pode ser redutível por uma máquina H em tempo polinomial.
Segundo o texto Haplotype Inference
, a Inferência de Haplótipos por Pura Parcimônia foi sujerido pela primeira vez por Earl Hubbell que procou que sua complexidade é NP-difícil, portanto a opção A não é a resposta desta questão.
Ainda segundo o texto Haplotype Inference, a Inferência de Haplótipos por Resolução Máxima também foi provado ser NP-difícil, invalidando assim também a opção B desta questão.
A programação Linear Inteira para problemas binários (0 e 1) também é NP-difícil, onde descartamos também a opção D.
A Inferência de Haplótipos por Filogenia Perfeita, segundo o livro Introduction to Computacional Molecular Biology, possui uma complexidade NP-completa, pois o algoritmo é executado num tempo polinomial de n, m e r, sendo que esta é a resposta correta, portanto a alternativa C.
Colega Alexandre,
ResponderExcluirSeu comentário não corresponda à realidade. Você parece ter confundido o problema de Filogenia Perfeita com entradas sendo matrizes de características x espécies (estudado no livro Introduction to Computational Molecular Biology, de Setubal e Meidanis) com o problema de Filogenia Perfeita com entradas sendo haplótipos. Apesar do primeiro ser NP-difícil (ou NP-completo, em sua versão de decisão), o segundo é polinomial.
Além disso, vejo em sua resposta algumas falhas em relação a complexidade computacional. Mistura algoritmo com problema, comete alguns erros com a descição correta dos termos, enfim, um texto onde você tentou sinceramente (percebo isto) entender o que está por trás destas noções todas de complexidade, mas não conseguiu ser claro nem correto.
Sua nota será 4,0 (quarto). Conseguiu acertar a alternativa correta, mas não pela razão correta: o problema de Inferência de Haplótipos por filogenia perfeita é polinomial.