from typing import Dict, List, Tuple, Optional, Set
from dataclasses import dataclass
import networkx as nx
import matplotlib.pyplot as plt
@dataclass
class Problema:
"""Representa um problema computacional."""
nome: str
classe: str # 'P', 'NP', 'NP-completo', etc.
descricao: str
@dataclass
class Reducao:
"""Representa uma redução polinomial entre dois problemas."""
origem: str
destino: str
transformacao: Optional[Callable] = None
tempo_polinomial: bool = True
class RedeReducoes:
"""
Gerencia uma rede de problemas e suas reduções.
Permite verificar propriedades como NP-completude.
"""
def __init__(self):
self.problemas: Dict[str, Problema] = {}
self.reducoes: List[Reducao] = []
self.grafo = nx.DiGraph()
def adicionar_problema(self, problema: Problema):
"""Adiciona um problema ao sistema."""
self.problemas[problema.nome] = problema
self.grafo.add_node(problema.nome)
def adicionar_reducao(self, reducao: Reducao):
"""Adiciona uma redução entre dois problemas."""
if reducao.origem not in self.problemas or reducao.destino not in self.problemas:
raise ValueError("Problemas devem ser adicionados antes das reduções")
self.reducoes.append(reducao)
self.grafo.add_edge(reducao.origem, reducao.destino)
def existe_caminho_reducao(self, origem: str, destino: str) -> bool:
"""Verifica se existe uma cadeia de reduções de origem para destino."""
return nx.has_path(self.grafo, origem, destino)
def verificar_np_completude(self, problema: str) -> Tuple[bool, str]:
"""
Verifica se um problema é NP-completo baseado em:
1. Está em NP
2. Todo problema em NP reduz a ele (via transitividade)
"""
if problema not in self.problemas:
return False, "Problema não encontrado"
p = self.problemas[problema]
# Verificar se está em NP
if p.classe not in ['NP', 'NP-completo']:
return False, f"Problema está em {p.classe}, não em NP"
# Verificar se existe algum NP-completo conhecido que reduz a ele
np_completos_conhecidos = [nome for nome, prob in self.problemas.items()
if prob.classe == 'NP-completo']
if not np_completos_conhecidos:
return False, "Nenhum problema NP-completo conhecido no sistema"
# Se algum NP-completo reduz a este problema, ele também é NP-completo
for npc in np_completos_conhecidos:
if self.existe_caminho_reducao(npc, problema):
return True, f"NP-completo via redução de {npc}"
return False, "Não foi possível estabelecer NP-completude"
def simular_reducao_3sat_clique(self, formula_cnf: List[List[str]]) -> Tuple[Set, int]:
"""
Simula a redução clássica de 3-SAT para CLIQUE.
Args:
formula_cnf: Lista de cláusulas, cada cláusula é lista de literais
Returns:
Grafo como conjunto de arestas e valor k para o problema CLIQUE
"""
vertices = []
for i, clausula in enumerate(formula_cnf):
for literal in clausula:
vertices.append((i, literal))
# Criar arestas: conectar vértices de cláusulas diferentes
# que não são literais contraditórios
arestas = set()
for v1 in vertices:
for v2 in vertices:
if v1 != v2:
clausula1, lit1 = v1
clausula2, lit2 = v2
# Vértices de cláusulas diferentes
if clausula1 != clausula2:
# Literais não contraditórios
if not (lit1 == f"¬{lit2}" or lit2 == f"¬{lit1}"):
if lit1.replace('¬', '') != lit2.replace('¬', '') or lit1 == lit2:
arestas.add(tuple(sorted([str(v1), str(v2)])))
k = len(formula_cnf) # Precisamos de um clique de tamanho m (número de cláusulas)
return arestas, k
def visualizar_rede(self):
"""Visualiza a rede de reduções como um grafo direcionado."""
plt.figure(figsize=(12, 8))
# Definir cores baseadas nas classes
color_map = {
'P': 'lightgreen',
'NP': 'lightblue',
'NP-completo': 'lightcoral',
'PSPACE': 'lightyellow'
}
node_colors = [color_map.get(self.problemas[node].classe, 'lightgray')
for node in self.grafo.nodes()]
pos = nx.spring_layout(self.grafo, k=2, iterations=50)
nx.draw(self.grafo, pos, node_color=node_colors, with_labels=True,
node_size=2000, font_size=10, font_weight='bold',
arrows=True, arrowsize=20, edge_color='gray')
plt.title("Rede de Reduções entre Problemas")
plt.axis('off')
plt.tight_layout()
return plt
# TAREFA: Complete a implementação
def main():
"""
Tarefa: Implemente um exemplo completo que:
1. Crie uma rede com pelo menos 7 problemas conhecidos (SAT, 3-SAT, CLIQUE, etc.)
2. Adicione as reduções clássicas entre eles
3. Verifique a NP-completude de diferentes problemas
4. Simule pelo menos uma redução concreta (ex: 3-SAT para CLIQUE)
5. Visualize a rede de reduções
"""
rede = RedeReducoes()
# Exemplo inicial (complete e expanda)
sat = Problema("SAT", "NP-completo", "Satisfatibilidade booleana")
three_sat = Problema("3-SAT", "NP-completo", "SAT com 3 literais por cláusula")
clique = Problema("CLIQUE", "NP", "Encontrar clique de tamanho k")
rede.adicionar_problema(sat)
rede.adicionar_problema(three_sat)
rede.adicionar_problema(clique)
# Adicione reduções
rede.adicionar_reducao(Reducao("SAT", "3-SAT"))
rede.adicionar_reducao(Reducao("3-SAT", "CLIQUE"))
# TODO: Adicione mais problemas e reduções
# Sugestões: VERTEX-COVER, INDEPENDENT-SET, HAMILTONIAN-CYCLE, TSP, SUBSET-SUM
# Teste a redução 3-SAT para CLIQUE
formula = [['x', 'y', 'z'], ['¬x', 'y', '¬z'], ['x', '¬y', 'z']]
arestas, k = rede.simular_reducao_3sat_clique(formula)
print(f"Fórmula 3-SAT: {formula}")
print(f"Grafo resultante tem {len(arestas)} arestas")
print(f"Procurando clique de tamanho {k}")
# TODO: Complete a implementação
print("\nImplementação a ser completada...")
if __name__ == "__main__":
main()