Classes de Complexidade - Desafios Flashcards
Todo problema em P também está em NP. Verdadeiro ou Falso? Justifique.
Verdadeiro. Todo problema resolvível em tempo polinomial também pode ter sua solução verificada em tempo polinomial usando o próprio resolvedor.
Existem problemas NP-completos que não podem ser resolvidos por força bruta. Verdadeiro ou Falso? Justifique.
Falso. O problema de SAT pode ser resolvido na força-bruta. Visto que todos os problemas NP-Completos podem ser reduzidos a ele, todo problema NP por consequência pode ser resolvido por força-bruta.
Todos os problemas em co-NP também estão em NP. Verdadeiro ou Falso? Justifique.
Falso. Não sabemos se NP=co−NP, portanto nem todos os problemas em co-NP estão em NP.
Se P=NP, todos os problemas NP-difíceis estão em P. Verdadeiro ou falso? Justifique.
Falso. Contra-exemplo: o problema da parada é um problema NP-difícil (todo problema em NP pode ser reduzido para ele), porém sabemos que não existe nenhum algoritmo capaz de resolvê-lo.
Todo problema NP-difícil é também NP-completo. Verdadeiro ou falso? Justifique.
Falso. Contra-exemplo: o problema da parada é um problema NP-difícil e é indecidível.
Se um algoritmo resolve satisfatibilidade (SAT) em tempo polinomial, ele resolve todos os problemas NP-completos. Verdadeiro ou falso? Justifique.
Verdadeiro. Todo problema NP pode ser reduzido ao problema SAT com uma quantidade polinomial de etapas. Se o problema SAT for resolvível em tempo polinomial, qualquer problema NP pode ser resolvido em tempo polinomial usando a redução combinada com a solução do problema SAT.
Reduções são sempre necessárias para provar que um problema é NP-completo.
Verdadeiro. Um problema é NP completo se e somente se qualquer outro problema NP pode ser reduzido a ele em tempo polinomial.
Qual é a condição necessária para um problema ser NP-completo?
(a) Estar em P
(b) Outro problema NP-completo ser redutível a ele
(c) Ser solucionável em tempo exponencial
(d) Ser verificável em tempo logarítmico
(b) Outro problema NP-completo ser redutível a ele
Qual é a principal diferença entre P e NP?
(a) P contém problemas mais difíceis que NP
(b) Soluções em P podem ser verificadas em tempo exponencial
(c) P é resolvido em tempo polinomial, enquanto NP é apenas verificável em tempo polinomial
(d) Não há diferença entre P e NP
(c) P é resolvido em tempo polinomial, enquanto NP é apenas verificável em tempo polinomial
Qual é um exemplo de problema em P?
(a) Multiplicação de dois números inteiros
(b) SAT
(c) Mochila 0-1
(d) Caixeiro viajante
(a) Multiplicação de dois números inteiros
Qual é o primeiro passo para provar que um problema é NP-completo?
(a) Demonstrar que ele está em P
(b) Reduzir outro problema NP-completo a ele
(c) Mostrar que ele está em NP
(d) Encontrar uma solução para ele
(c) Mostrar que ele está em NP
Se P=NP, qual das seguintes afirmações é verdadeira?
(a) Todo problema em NP pode ser resolvido em tempo polinomial
(b) Apenas problemas em P podem ser verificados em tempo polinomial
(c) Todos os problemas NP-completos tornam-se NP-difíceis
(d) Isso não afeta problemas em co-NP
(a) Todo problema em NP pode ser resolvido em tempo polinomial
Qual das seguintes não é uma característica de NP?
(a) Verificabilidade em tempo polinomial
(b) Solubilidade garantida em tempo polinomial
(c) Inclusão de problemas NP-completos
(d) Subconjunto de NP-difícil
(b) Solubilidade garantida em tempo polinomial
Qual é o propósito das reduções polinomiais?
(a) Melhorar a eficiência de algoritmos
(b) Provar relações de complexidade entre problemas
(c) Encontrar soluções exatas para problemas NP-difíceis
(d) Resolver problemas co-NP
(b) Provar relações de complexidade entre problemas
Qual é a principal aplicação prática da teoria de NP-completude?
(a) Provar que um problema não tem solução
(b) Determinar a dificuldade relativa de problemas computacionais
(c) Resolver problemas de decisão em tempo exponencial
(d) Demonstrar que P é diferente de NP
(b) Determinar a dificuldade relativa de problemas computacionais
O que é necessário para mostrar que um problema está em NP?
(a) Uma solução deve ser verificável em tempo polinomial
(b) Deve ser redutível a outro problema NP-completo
(c) Deve estar em co-NP
(d) Deve ter uma solução única
(a) Uma solução deve ser verificável em tempo polinomial
Explique a diferença entre problemas NP-completos e NP-difíceis.
Problemas NP-completos são aqueles que pertencem à classe NP e são, ao mesmo tempo, tão difíceis quanto qualquer outro problema em NP, ou seja, qualquer problema em NP pode ser reduzido a eles em tempo polinomial. Já os problemas NP-difíceis são, por definição, pelo menos tão difíceis quanto os problemas em NP, mas podem não pertencer à classe NP, ou seja, podem não ser verificáveis em tempo polinomial.
Por que a redução polinomial é essencial na teoria da complexidade?
A redução polinomial permite comparar a dificuldade relativa de problemas computacionais. Se um problema pode ser reduzido a outro em tempo polinomial, isso implica que resolver o segundo problema fornece uma solução eficiente para o primeiro. É uma ferramenta fundamental para provar que um problema é NP-completo, pois conecta problemas de diferentes áreas por sua dificuldade.
Descreva como o Teorema de Cook-Levin formaliza a NP-completude.
O Teorema de Cook-Levin demonstra que o problema SAT (satisfatibilidade booleana) é NP-completo, provando que qualquer problema em NP pode ser reduzido em tempo polinomial ao SAT. Isso formaliza a definição de NP-completude e estabelece o SAT como o “primeiro” problema NP-completo, permitindo que outros problemas sejam comparados a ele.
Como a classe co-NP complementa a classe NP?
A classe co-NP é composta por problemas cujas respostas negativas podem ser verificadas em tempo polinomial. É o complemento de NP no sentido lógico: se um problema está em NP, seu complemento é co-NP. Ainda não se sabe se NP = co−NP, mas entender essa relação ajuda na classificação de problemas difíceis.
Por que a maioria dos problemas práticos pertencem à classe NP?
Muitos problemas práticos pertencem a NP primeiro porque todo problema P também pertence a NP. Segundo, embora encontrar uma solução possa ser difícil, verificar se uma solução é válida geralmente é direto e pode ser feito em tempo polinomial. Exemplos incluem problemas de logística, planejamento e otimização.
Explique a diferença entre verificabilidade e solubilidade em relação às classes de complexidade.
Verificabilidade refere-se à capacidade de checar se uma solução fornecida está correta em tempo polinomial, o que define os problemas em NP. Solubilidade, por outro lado, diz respeito à capacidade de encontrar uma solução em tempo polinomial, o que define os problemas em P.
Como a teoria de complexidade impacta a otimização de algoritmos na prática?
A teoria de complexidade ajuda a identificar quais problemas podem ser resolvidos eficientemente (em P), quais são intratáveis (NP-completos) e quais são impossíveis(NP-difíceis). Isso orienta desenvolvedores a buscar soluções aproximadas, heurísticas ou métodos específicos para casos especiais quando problemas intratáveis surgem, otimizando recursos computacionais.
Construa uma redução do problema de Independent Set para o problema do Vertex Cover. Qual a relação entre esses problemas?
Dado um conjunto independente X de um conjunto U, conjunto U - X é uma solução para o problema do Vertex Cover. São problemas equivalentes
Construa uma redução do problema do Vertex Cover para o problema do Set Cover. Qual a relação entre esses problemas?
Dado um conjunto universo U que contém todas as arestas do grafo, defina os subconjuntos A1, A2, …, An como sendo todas as arestas incidentes ao vértice 1, 2, …, n. A solução do Set Cover nos dá os subconjuntos que contém todas as arestas; os vértices correspondentes são a solução do Vertex Cover. Vertex Cover <= p Set Cover.
Construa uma redução do problema do 3-SAT para o problema do Independent Set. Qual a relação entre esses problemas?
Construa o seguinte grafo a partir do 3-SAT:
- Cada cláusula é representada por um vértice
- Arestas representam cláusulas conectadas: unem tanto vértices na mesma cláusula no 3-SAT quanto vértices e seus opostos lógicos em outras cláusulas.
Uma solução para o problema do Independent Set de tamanho N (sendo N o número de cláusulas independentes do 3-SAT) é também uma solução (mas não a única) para o 3-SAT.
3-SAT <= P Independent Set
Qual a diferença entre um problema de existência, encontrar e otimização? Qual a relação entre eles?
Existência: Existe uma solução para esse problema?
Encontrar: Encontre uma solução para esse problema de tamanho N.
Otimização: Encontre a menor solução possível para esse problema.
São problemas que podem ser mutuamente reduzidos em tempo polinomial.
