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?
Improve this question
$\endgroup$
3
  • 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
    Commented Nov 13, 2016 at 9:00
  • 1
    $\begingroup$ Please ask only one question per post. $\endgroup$
    – Raphael
    Commented Nov 13, 2016 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$
    – Revolucion for Monica
    Commented Nov 13, 2016 at 23:13

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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