New answers tagged polynomial-time
12
Concerning Question 1, there have mainly been two lines of work to find tractable restrictions of SAT.
The first one that you are already familiar with is to restrict the types of the clauses that you are allowed to use. For example, in 2-SAT, you are only allowed to use size two clauses. In Horn-SAT, you only allow Horn clauses etc. The tractable ...
3
Path with minimum weight gap: This can be solved in time $\tilde{O}(|E|^2)$, where $|E|$ is the number of edges (assuming $|E|$ is at least linear in the number of vertices). You can loop over the minimum weight, and do binary search (or efficient updates) over the maximum weight, and check connectivity. I do not know whether this can be improved.
Path ...
Top 50 recent answers are included
