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
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&nbsp;$\mathrm{P}$ are classes of problems, not algorithms.