Give an NL-algorithm for complement of 2-SAT

Question

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

Answer 1

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.

Answer 2

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.