# 歸約

Example of a reduction from the boolean satisfiability problem (AB) ∧ (¬A ∨ ¬B ∨ ¬C) ∧ (¬ABC) to a vertex cover problem. The blue vertices form a minimum vertex cover, and the blue vertices in the gray oval correspond to a satisfying truth assignment for the original formula.

## 簡易介紹

${\displaystyle a\times b={\frac {\left(\left(a+b\right)^{2}-a^{2}-b^{2}\right)}{2}}}$

${\displaystyle a^{2}=a\times a}$

## 定義

${\displaystyle \exists f\in F{\mbox{ . }}\forall x\in \mathbb {N} {\mbox{ . }}x\in A\Leftrightarrow f(x)\in B}$

${\displaystyle A\leq _{F}B}$

SP(N)（即自然数集的幂集）的子集，另設≤的歸約關係，則S稱做封閉於≤之下若：

${\displaystyle \forall s\in S{\mbox{ . }}\forall A\in P(\mathbb {N} ){\mbox{ . }}A\leq s\Leftrightarrow A\in S}$

N的子集A，稱對S困難（hard），若：

${\displaystyle \forall s\in S{\mbox{ . }}s\leq A}$

N的子集A，若AS困難且A包含於S集合之內，則稱A對S完備（complete）

## 参考文献

1. ^ 例如：存档副本. [2007-01-06]. （原始内容存档于2007-01-17）.
2. ^ Thomas H. Cormen, Introduction to Algorithm, second edition, page. 970, figure 34.1.

## 文獻

• （英文） Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, Second Edition, 2001, ISBN 978-0-262-03293-3
• （英文） Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967, ISBN 978-0-262-68052-3.
• （英文） Peter Bürgisser: Completeness and Reduction in Algebraic Complexity Theory, Springer, 2000, ISBN 978-3-540-66752-0.
• （英文） E.R. Griffor: Handbook of Computability Theory, North Holland, 1999, ISBN 978-0-444-89882-1.