Pergunta

Hello everyone this is my first question ever and I apologize if I ask in the wrong manner causing this post to be either closed or deleted. I'm learning Reductions and my professor has asked us to write a paper on reductions (3SAT)

When doing the Reduction from the Clique Problem to 3SAT, I understand that we make clauses and every clause contains 3 literals (hence, 3SAT) but my problem comes when choosing what literals and why they choose them. How do I know which literals to choose? So I know that in every clause I'll have x1, x2 and x3, but how do I choose their assignment order? In one clause I have (x1 or x2 or x3) and in another I have (x1 or not x2 or not x3). How were these chosen?

Also, it seems they don't begin with a graph in mind already. What if I'm given a graph to begin with, how would I convert it into x1, x2, x3? If for clause I have 3 vertices, how would I assign them their respected boolean expression? Thank you very much

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top