A polynomial-time reduction transforms instances of one computational problem into instances of another using a polynomial-time algorithm.
A polynomial-time many-one reduction from a decision problem to a decision problem is a polynomial-time computable function satisfying exactly when .
Given finitely encoded nonnegative integers and target , the subset sum problem asks whether some subset sums to . Taking equal item weights and profits reduces it to testing whether a 0-1 knapsack problem with capacity attains value .
Maximum 2-satisfiability asks for an assignment satisfying as many clause occurrences as possible when every nonempty clause has at most two literals. Occurrences are counted even when a clause is repeated. Its decision problem is NP-complete by the seven-clause gadget for MAX-2SAT, while the method of conditional probabilities gives a polynomial-time half approximation.
When each variable appears in at most one normalized singleton clause, satisfy that favored literal with probability and choose independent variables. Every proper binary clause is then satisfied with probability at least , and every singleton with probability . Maximize the common lower bound by , giving the reciprocal of the golden ratio. The method of conditional probabilities derandomizes the construction, obtaining approximation ratio . Tautologies are harmless; the singleton restriction must be applied after removing repeated literals within clauses.
A three-literal disjunction can be represented by ten unit or two-literal clause occurrences with one fresh auxiliary variable. If the number of true input literals is zero, the best auxiliary choice satisfies six; for , the best count is seven. Applying separate gadgets to all clauses of a 3-SAT instance gives target seven times the original clause count, proving NP-completeness of the decision form of MAX-2SAT. The local counting argument is essential: no gadget may exceed seven and compensate for an unsatisfied input clause.
A Boolean formula is a finite expression built from Boolean variables and Boolean operations. A choice of truth values determines its value. The Boolean satisfiability problem asks whether some choice makes it true.
A Boolean formula is in conjunctive normal form when it is a conjunction of Boolean clauses. It is true precisely when every clause is true; an empty conjunction is true. 3-SAT restricts each clause to at most three Boolean literals.
A clause is an expression formed from Boolean literals, true when at least one literal is true. The empty clause is false. Repeating a literal does not change the truth value. A conjunctive normal form formula is a conjunction of these clauses.
A Boolean literal is a Boolean variable or its negation . The two literals have opposite truth values. A Boolean clause combines literals, and a Boolean-pair colouring gadget represents a variable and its negation by two vertices with opposite Boolean colours.
A Boolean variable takes one of two truth values. It is an input to a Boolean formula; a Boolean literal uses the variable either positively or negated.
3-SAT is the Boolean satisfiability problem restricted to Boolean formulas in conjunctive normal form with at most three Boolean literals per Boolean clause. It is NP-complete. A nonempty short Boolean clause can be padded to three positions by repeating a Boolean literal, without changing satisfiability.
A Horn clause is a disjunction of literals containing at most one positive literal. It can be read as an implication whose antecedent is a conjunction of variables.
Horn-SAT asks whether a conjunction of Horn clauses is satisfiable.
The Horn-SAT forward-chaining algorithm starts with every variable false and repeatedly makes the conclusion of any enabled implication true. It reports failure if it enables a clause with no positive conclusion; otherwise the fixed point is the least satisfying assignment.
Quadratic-equation satisfiability over asks whether a finite system of polynomial equations of degree at most two over the finite field has a common solution.
Articles by others on the same topic
Polynomial-time reduction is a concept in computational complexity theory that describes a way to show that one problem can be transformed into another problem in polynomial time. It serves as a fundamental technique for classifying the difficulty of computational problems and understanding their relationships. ### Key Concepts: 1. **Problem Mapping**: In polynomial-time reduction, we have two problems, let's say Problem A and Problem B. We want to show that Problem A is at most as hard as Problem B.