Classes de Complexidade - Fundamentos Flashcards
O que são classes de complexidade?
São categorias que agrupam problemas computacionais com base nos recursos necessários para resolvê-los, como tempo e espaço.
O que caracteriza a classe P?
É o conjunto de problemas que podem ser resolvidos em tempo polinomial por uma máquina determinística.
O que caracteriza a classe NP?
É o conjunto de problemas cujas soluções podem ser verificadas em tempo polinomial por uma máquina determinística.
Qual é a relação entre P e NP?
Não se sabe se P=NP, mas sabemos que P⊆NP.
O que significa NP na classe NP?
Significa Nondeterministic Polynomial time (tempo polinomial não determinístico).
O que é uma redução em teoria da complexidade?
É uma forma de transformar um problema em outro, preservando a dificuldade relativa entre eles.
Qual é o propósito de uma redução polinomial?
Mostrar que a solução de um problema pode ser usada para resolver outro problema de forma eficiente.
O que significa A≤pB em reduções polinomiais?
ignifica que o problema A pode ser reduzido ao problema B em tempo polinomial.
Qual é a importância das reduções para a teoria de NP-completude?
Elas ajudam a provar que um problema é tão difícil quanto outro já conhecido.
O que é uma redução por transformação?
É uma redução que converte diretamente as instâncias de um problema em instâncias de outro.
O que significa um problema ser NP-completo?
É um problema que está em NP e para o qual todo problema em NP pode ser reduzido em tempo polinomial.
Como provar que um problema é NP-completo?
Mostrando que ele está em NP e que um problema NP-completo conhecido pode ser reduzido a ele em tempo polinomial.
O que é um problema NP-difícil?
É um problema para o qual todo problema em NP pode ser reduzido, mas ele mesmo pode não estar em NP.
Qual é a diferença entre NP e NP-completo?
NP é uma classe de problemas verificáveis em tempo polinomial, enquanto NP-completo contém os problemas de NP para os quais todos os outros problemas de NP podem ser reduzidos.
Qual foi o primeiro problema provado como NP-completo?
O problema SAT (satisfatibilidade booleana).
Como um problema NP-completo pode ser resolvido?
Usando métodos exatos (como força bruta), aproximação, ou algoritmos heurísticos.
Por que a NP-completude é importante na prática?
Ela ajuda a entender quais problemas provavelmente não têm soluções eficientes e onde buscar aproximações ou heurísticas.
O que caracteriza problemas intratáveis? Qual a diferença entre um problema intratável e um problema indecidível?
Problemas intratáveis são problemas para os quais não existe um algoritmo eficiente, ou seja, resolvê-los requer tempo superpolinomial para grandes entradas. Problemas indecidíveis, por sua vez, são problemas para os quais não existe um algoritmo capaz de resolvê-los.
O que significa tempo polinomial?
Tempo de execução de um algoritmo que pode ser expresso como uma função polinomial do tamanho da entrada.
Qual a diferença entre tempo polinomial e tempo pseudo-polinomial?
Tempo polinomial é polinomial em função do tamanho da entrada. Pseudo-polinomial é polinomial em função do valor; visto que esse valor é armazenado em bits binários, um problema pseudo-polinomial é na verdade exponencial em função da quantidade de bits usados.
Qual é a diferença entre uma redução polinomial e uma redução geral?
Uma redução polinomial transforma instâncias de um problema em outro em tempo polinomial, enquanto uma redução geral pode não ter essa restrição.
Por que a classe NP é importante?
Porque contém muitos problemas práticos cuja solução é fácil de verificar, mas difícil de encontrar.
O que é uma prova certificável?
É uma prova que pode ser verificada em tempo polinomial por um algoritmo.
Qual é a relação entre NP e co-NP?
Co-NP é a classe de problemas cujas respostas negativas podem ser verificadas em tempo polinomial.
Cite e explique três aplicações para as reduções polinomiais.
Construção de algoritmos: Se X ≤ P Y e Y pode ser resolvido em tempo polinomial, X pode ser resolvido em tempo polinomial usando-se de uma redução para Y
Estabelecer intratabilidade: Se X ≤ P Y e X não pode ser resolvido em tempo polinomial, Y não pode ser resolvido em tempo polinomial.
Estabelecer equivalência: Se ambos X ≤ P Y e Y ≤ P X, podemos usar a notação X ≡ P Y para dizer que X pode ser resolvido em tempo polinomial se e somente se Y também pode.
O que significa dizer que um algoritmo C é um certificador para o problema X?
Significa dizer que, para cada string s, s ∈ X se e somente se existe uma string t tal que C(s, t) = sim. Em outras palavras, quer dizer que o algoritmo consegue verificar se t é uma prova de que s se enquadra no problema X.
Qual a diferença entre uma redução polinomial e uma transformação polinomial? Qual a relação entre eles? São conceitos equivalentes?
Uma redução polinomial de X para Y resolve o problema X usando um número polinomial de etapas e uma quantidade polinomial de chamadas ao oráculo que resolve Y. Uma transformação polinomial de X para Y converte o problema X em uma instância do problema Y. Na prática, uma transformação polinomial é uma redução polinomial que usa uma única vez o algoritmo que resolve Y. Fora isso, não se sabe se são definições equivalentes.
