<p>It is a very basic exercise for undergraduate/graduate courses in Theoretical computer Science, and I think books avoid giving the solution so that students do not copy it without understanding. Here are some hints which might put you on the path to the solution:</p>
<ol>
<li>Remember the definition of 2-SAT;</li>
<li>Remember the logical definition of A =&gt; B in term of 'not', 'and' and 'or' operators;</li>
<li>See how you would solve an instance of 2-SAT &quot;by hand&quot;, without trying to do so in linear time (but still trying to be efficient);</li>
<li>Analyze the running time of your algorithm to solve a 2-SAT instance (hopefully it should be at least polynomial);</li>
<li>Remember how many dimensions are used by the tables in dynamic programs running in linear time;</li>
<li>Think about the size of a table of the same number of dimension which could solve a 2-SAT instance (i.e. is it as big as a function of the number of variables or of the number of clauses);</li>
<li>Deduce a dynamic program solving a 2-SAT instance in linear time (and space).</li>
</ol>
<p>Hopefully you don't hate this answer because, voluntarily, it avoids giving you the solution! I tried to put just the right amount of hints towards the solution so that you could get unstuck if you are, but with enough room for you (and other future readers) to still learn from the experience!</p>

CC BY-SA 4.0
2023-03-01T10:56:27.017Z
2023-03-01T10:56:27.017Z
J.y B.y
<p>Would anyone have any sources that describe/an explanation of how solving 2-SAT using dynamic programming takes a linear amount of time? Can't seem to find a text that proves it in detail/formality. My first guess would be that somehow the satisfiability of sub-clauses is stored for later reference, but I'm not completely sure. Any help is appreciated!</p>
<p>(First time posting, apologies if this is the wrong place/format)</p>

CC BY-SA 4.0
2023-03-01T10:46:25.640Z
This is not really a research question, and runs the risk to be seen as a homework question. Maybe you could explain the context in which you fell on this question to convince people that you are not just a student asking on stackexchange for the solution to their homework (no offense meant if you are, but then checkout https://cstheory.stackexchange.com/tour, and maybe consider asking on https://cs.stackexchange.com/ ?)
J.y B.y
CC BY-SA 4.0
2023-03-01T15:34:48.933Z
Oh alright! Thanks for pointing me to the right place and for your kind answer. To be honest, yes it was a homework question. I'll ask on cs stackexchange.
wtfamidoing
CC BY-SA 4.0
2023-03-02T06:33:15.850Z
Cross-posted: https://cstheory.stackexchange.com/q/52530/5038, https://cs.stackexchange.com/q/157830/755, https://stackoverflow.com/q/75606382/781723.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).
D.W.
<cc.complexity-theory><sat><proofs><dynamic-programming>
Sources that prove solving 2-SAT with DP takes linear time
wtfamidoing
# Sources that prove solving 2-SAT with DP takes linear time

(Asked by: username_0 on 2023-02-28)

Would anyone have any sources that describe/an explanation of how solving 2-SAT using dynamic programming takes a linear amount of time? Can't seem to find a text that proves it in detail/formality. My first guess would be that somehow the satisfiability of sub-clauses is stored for later reference, but I'm not completely sure. Any help is appreciated!

(First time posting, apologies if this is the wrong place/format)

**Tags:** cc.complexity-theory, sat, proofs, dynamic-programming
> **Comments:**
> **username_1**: This is not really a research question, and runs the risk to be seen as a homework question. Maybe you could explain the context in which you fell on this question to convince people that you are not just a student asking on stackexchange for the solution to their homework (no offense meant if you are, but then checkout https://cstheory.stackexchange.com/tour, and maybe consider asking on https://cs.stackexchange.com/ ?)  
> **username_0**: Oh alright! Thanks for pointing me to the right place and for your kind answer. To be honest, yes it was a homework question. I'll ask on cs stackexchange.  
> **username_2**: Cross-posted: https://cstheory.stackexchange.com/q/52530/5038, https://cs.stackexchange.com/q/157830/755, https://stackoverflow.com/q/75606382/781723.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  

---

## 1 answers

### Answer by username_1 on 2023-03-01. Score: 3

It is a very basic exercise for undergraduate/graduate courses in Theoretical computer Science, and I think books avoid giving the solution so that students do not copy it without understanding. Here are some hints which might put you on the path to the solution:

1. Remember the definition of 2-SAT;
2. Remember the logical definition of A => B in term of 'not', 'and' and 'or' operators;
3. See how you would solve an instance of 2-SAT "by hand", without trying to do so in linear time (but still trying to be efficient);
4. Analyze the running time of your algorithm to solve a 2-SAT instance (hopefully it should be at least polynomial);
5. Remember how many dimensions are used by the tables in dynamic programs running in linear time;
6. Think about the size of a table of the same number of dimension which could solve a 2-SAT instance (i.e. is it as big as a function of the number of variables or of the number of clauses);
7. Deduce a dynamic program solving a 2-SAT instance in linear time (and space).

Hopefully you don't hate this answer because, voluntarily, it avoids giving you the solution! I tried to put just the right amount of hints towards the solution so that you could get unstuck if you are, but with enough room for you (and other future readers) to still learn from the experience!


---

