NL-complete problems are a class of decision problems that are both in the complexity class NL (nondeterministic logarithmic space) and are as hard as the hardest problems in NL. The concept of NL-completeness is similar to that of NP-completeness, but with respect to problems that can be solved using a restricted amount of memory.
2-Satisfiability, often abbreviated as 2-SAT, is a decision problem in computer science and mathematical logic that involves determining the satisfiability of a boolean formula expressed in conjunctive normal form (CNF) with exactly two literals per clause. In formal terms, a 2-SAT formula consists of a conjunction (AND) of clauses, where each clause is a disjunction (OR) of exactly two literals. A literal is a variable or its negation.
Articles by others on the same topic
There are currently no matching articles.