1
$\begingroup$

A 2-clause is a clause with at most two propositions (clauses?) : $(p \wedge q,\neg p \wedge q, \neg p,...)$. I have to show that the folllowing problem is $\in$ P:

2-SAT: Input : A conjunction $\Phi$ of 2-clauses. Question : Is it satisfisable?

For each set of 2-clause $C$ we associate $G_C$ defined as

  • $V_{G_C}$ contains two vertices $x$ and $\neg x$ for each variables in $C$.
  • $E_{G_C}$ contains an edge $\alpha \rightarrow \beta$ if and only if $\neg \alpha \vee\beta$ or $\beta \vee\neg\alpha$ is in $C$.

This graph should help me show this problem belongs to P. Yet,

  • Why is $C$ satisfiable if and only if $G_C$ doesn't have any loop?
  • Why does $G_C$ space is polynomial?
  • Why is $G_C$ calculation from $C$ is polynomial?
$\endgroup$
  • 1
    $\begingroup$ This problem is general reference. Where have you looked for explanations? What have you tried towards answering your questions? (Please polish the language some: using multiple verbs per sentence makes them hard to understand.) $\endgroup$ – Raphael Nov 13 '16 at 9:00
  • 1
    $\begingroup$ Please ask only one question per post. $\endgroup$ – Raphael Nov 13 '16 at 9:00
  • $\begingroup$ @Juho As far as we have at each stage 2 possibilites, don't we create $2^n$ possbilities with $n$ the number of 2-clauses? $\endgroup$ – ThePassenger Nov 13 '16 at 23:13
1
$\begingroup$

You already have a description of how the graph is built from the formula. Think about a possible algorithm for doing the job. For example, you first scan over all variables in the formula, and you add two vertices into your graph for each. Now you only need to add in the edges into the graph. You can scan over the clauses, and if you see either form you describe, you add in an edge into your graph. This all can be implemented to run in polynomial time; just observe you are performing two scans over the formula, and you do a bit of work for every step of the scan. Similar reasoning will make you see the graph only needs polynomial space.

For your first question, an answer is given in the Wikipedia article on 2-SAT, but has also been touched upon in other question (see e.g., here).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.