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