It is known that PATH (given a directed graph G and two vertices s,t is there a path in G from s to t), and 2SAT are NL-complete problems. Find a logspace reduction from PATH to 2SAT.
I know that 2-SAT is solvable in polynomial time and 2-SAT is NP-Hard.
I have issue about this statement: MAX 2-SAT is polynomial-time reducible to 2-SAT. Can you explain to me how reduction looks like? I need the only intution about that, but not proof.
I’m new in complexity theory and have to work on this algorithm, any insight on what is wrong or missing to respond correctly would be really appreciated.
- Describe the non-deterministic algorithm in pseudo-code.
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
- Prove its correctness.
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.
- Show that it only requires logarithmic space.
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
I’ve been developing interest in complexity classes and thought I was unable to prove my problem is NP hard, so I wanted to see if it was P-hard. I wanted to see if my puzzle solving is special. I have linked a previous question of mine to help clarify what is mentioned below. Explained here
Random Instance of 2-SAT used for attempt reduction
I took an instance of my problem X
Let’s say my problem X is determining if a puzzle is valid for my language
Instance of X
a = shift(L) puzzle
¬ a = invalid puzzle
¬b = invalid puzzle
b = shift(L) puzzle
Reduction into Shorter Instance
This boolean expression is only checking for 2-sat. Being True (valid puzzle) or False (invalid puzzle).
My idea is that a deterministic machine will consider n^2 x n^2 puzzles as invalid if the lower right-hand box is not filled. My puzzles are solved in quadratic time when provided a puzzle with this n x n box. Any other puzzle will simply fail to be solved if it does not follow my language. I have used an algorithm that can determine in poly-time that those failed puzzles are invalid puzzles. Because, the solver will not know it as an invalid puzzle. So it will try to map it out in my language thus giving an invalid puzzle.
I have the algorithm and proven that it works in poly-time, the problem is that I only know how to prove it by showing the algorithm. I just don’t know how to write it out mathematically. How would I properly do this?
I’ve been recently dealing with the classical problem of finding the minimum vertex cover in a bipartite graph. The common approach is to set direction to all edges and run DFS from all vertices of the left part outside of the matching. However, this solution seems too clever for me.
I read this in this link. Can any body explain it to me with simple example. https://codeforces.com/blog/entry/63164
” The minimum vertex cover should contain exactly one vertex for every edge in the maximum matching M. So let’s assign a boolean variable for every edge in M, say, xi = 0 if the i-th edge adds its left end to the vertex cover. One can build all the dependencies over these variables. For example, if there exist edges and , while w is not saturated by M, we have to set xi equal to 0, because there is no other way to cover the edge (u, w). All the other cases are handled trivially.
As a result, we obtain a full system of restrictions for the set of variables. Finding an arbitrary valid assignment is a classical 2-SAT problem. So we have basically reduced the minimum vertex cover problem to 2-SAT without thinking too much. “
what I dont understand is this
I don’t understand the variables. I have an edge from maximum matching then I might have both the endpoints of that edge in the vertex cover. But this scheme does not allow this.
And how to form 2-Sat for this graph?