# Give an NL-algorithm for complement of 2-SAT

Question1: What is the difference between 2SAT and the complement of 2SAT?

Question2: It is known that NL is contained in P, but what we know about P over NL? can be said that an algorithm that runs in P, uses NL space?

Information That I gather

I follow the Papadimitriou algorithm to solve 2-SAT with Let give 2-SAT a graph of connected nodes according to the specifications contained literal and clauses where the information of the nodes and connections is a container in a CNF of 2 literals per clause, because of the problem need to be contained in NL we assume that we are only working to solve this in 1 writing tape and 1 only input tape to run the algorithm

    for i=0 repeat log2(n times)
Choose Random initial assignment for every literal
Repeat 2n^2
-If
The assignment satisfies all the paths in the sequence
of clauses, Halt and report
-else
Pick arbitrary unsatisfied clauses and flip the value of its literals
Report unsatisfiable


According to 2-SAT reachability one condition for the possibility of no reach, if one path of the graph where there are connected nodes with the same literal and one of them is a negation, then the graph doesn't have a satisfiable result, and that would be the case in the algorithm. This is the same case for a complement of 2SAT.

In the non-deterministic solution, the algorithm could give only a correct answer or a false negative depending on the condition of the arrangement of the clauses, but never retrieve a false positive because of the condition establish in the conditional operator.

With the else clause the algorithms cover different possible clauses fliping the literal where the condition was unsatisfied and trying new options.

The algorithm uses only memory to keep the counter running because the counter corresponds to the size of the input in Log2(n)*2n^2 space on the writing tape.

Also is prove that 2SAT correspond to NL and NL-complete and we know that NL=coNL

• What is the question here? There is no question mark in the "question" text. – dkaeae May 27 '19 at 7:01
• We typically don’t check answers - this is your TA’s job. We can help if you have any specific doubts. – Yuval Filmus May 27 '19 at 7:45
• You're right, thanks for the clarification, will edit to be more specific about my doubts. – user2668676 May 27 '19 at 9:14

Question1: What is the difference between 2SAT and the complement of 2SAT?

The set of all strings that do not describe satisfiable 2CNF formulas.

Question2: It is known that NL is contained in P, but what we know about P over NL? can be said that an algorithm that runs in P, uses NL space?

We don't know anything significant beyond that $$\mathrm{NL}\subseteq\mathrm{P}$$.

It doesn't really make sense to ask if "an algorithm... uses NL space". You can ask if an algorithm uses logarithmic space and if it's nondeterministic, but there's no such thing as "nondeterministic space" per se. By that, I mean that the storage space itself isn't nondeterministic: nondeterminism is a property of the algorithm that uses the space.

It's certainly not true that an algorithm that runs in polynomial time necessarily uses logarithmic space: it could use polynomial space. It's possible that every deterministic algorithm that runs in polynomial time could be rewritten as a nondeterministic algorithm that uses only logarithmic space but we don't know if that's true or not. If it were true, we would have $$\mathrm{P}=\mathrm{NL}$$.

Note that, formally speaking, $$\mathrm{NL}$$ and $$\mathrm{P}$$ are classes of problems, not algorithms.

• Hi David. Thank you for the answers. About question 1, If that is the case then for CNF for 2SAT where you have literal and the negation of the literal in the same Clause or graph connection? I research about that's the case where you can define that 2SAT his unreachable or don't have a satisfiable answer. About question 2, thank for clarify the concept for me. – user2668676 May 27 '19 at 15:26

Assuming that P≠NL, we know that P-complete problems are not in NL. The prototypical example is the Circuit Evaluation Problem, in which you are given a circuit (with constants as inputs), and the goal is to determine whether it evaluates to true. Wikipedia describes many other P-complete problems.

Some problems are not (known to be) P-complete, yet we still believe they shouldn't belong to NL. For example, the complexity class CC sits between NL and P: NL⊆CC⊆P. It is believed that both inclusions are strict, and this implies that CC-complete propblems are not in NL. Examples include decision versions of the stable matching problem and the lexicographically first maximal matching problem.

Another example is the complexity class ⊕L, sitting between L and P, for which a complete problem is satisfiability of linear equations mod 2. There is not much information on this class, but it features in the refined Schaefer's theorem, and seems to be incomparable with NL (i.e., it is conjectured that none of the two classes contains the other).

Let me close with an important comment: NL=coNL. Therefore to show that a language is in NL, it suffices to show that its complement is in NL. The language 2SAT is known to be NL-complete, and in particular both 2SAT and its complement are in NL.