Karp Information

Any language $L_{1}$ ${\ displaystyle L_ {1}}$ $L_ {1}$ called reducible by Karp to the language $L_{2}$ ${\ displaystyle L_ {2}}$ $L_ {2}$ if function exists $F\colon \Sigma ^{*}\mapsto \Sigma ^{*}$ ${\ displaystyle F \ colon \ Sigma ^ {*} \ mapsto \ Sigma ^ {*}}$ ${\ displaystyle F \ colon \ Sigma ^ {*} \ mapsto \ Sigma ^ {*}}$ calculated in polynomial time, where F (x) belongs $L_{2}$ ${\ displaystyle L_ {2}}$ $L_ {2}$ if x belongs $L_{1}$ ${\ displaystyle L_ {1}}$ $L_ {1}$ . A language is called NP-hard if any NP class language reduces to it, and is called NP-complete if it is NP-hard and reduces itself to NP class. If there is an algorithm that solves an NP-complete problem in polynomial time, then all NP-problems are of class P.

Consider two languages $L_{1}$ ${\ displaystyle L_ {1}}$ $L_ {1}$ and $L_{2}$ ${\ displaystyle L_ {2}}$ $L_ {2}$ over the alphabets $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ and $\Gamma$ ${\ displaystyle \ Gamma}$ $\ Gamma$ . Information $L_{1}$ ${\ displaystyle L_ {1}}$ $L_ {1}$ to $L_{2}$ ${\ displaystyle L_ {2}}$ $L_ {2}$ Karp is a function $f\colon \Sigma ^{*}\mapsto \Gamma ^{*}$ ${\ displaystyle f \ colon \ Sigma ^ {*} \ mapsto \ Gamma ^ {*}}$ ${\ displaystyle f \ colon \ Sigma ^ {*} \ mapsto \ Gamma ^ {*}}$ computable in polynomial time such that $\forall x(x\in L_{1}\Leftrightarrow f(x)\in L_{2})$ ${\ displaystyle \ forall x (x \ in L_ {1} \ Leftrightrow f (x) \ in L_ {2})}$ ${\ displaystyle \ forall x (x \ in L_ {1} \ Leftrightrow f (x) \ in L_ {2})}$ . So informally language $L_{1}$ ${\ displaystyle L_ {1}}$ $L_ {1}$ "Not harder" language $L_{2}$ ${\ displaystyle L_ {2}}$ $L_ {2}$ .

If such a function $f$ ${\ displaystyle f}$ $f$ exists say that $L_{1}$ ${\ displaystyle L_ {1}}$ $L_ {1}$ reducible by Karp to $L_{2}$ ${\ displaystyle L_ {2}}$ $L_ {2}$ and write

L_{1}\leqslant _{K}L_{2}.

{\ displaystyle L_ {1} \ leqslant _ {K} L_ {2}.}

{\ displaystyle L_ {1} \ leqslant _ {K} L_ {2}.}

Note that Kap information is a special case of Cook information . In English sources, you can also find the name en: many-one reduction .

The PSPACE language class is the set of languages allowed by a deterministic Turing machine with a polynomial space constraint.

The NPSPACE language class is the set of languages allowed by a non-deterministic Turing machine with a polynomial space constraint.

Transitivity

The main property of Kap information is transitivity. If we represent languages as symbols, then we can consider them as a mathematical operation: Α> Β, Β> Ε → Α> Ε.

Links

The course "Introduction to the structural theory of complexity"
Hopkfroft J., Motvani R., Ulman J. Introduction to the theory of automata, languages and computations, 2nd ed .: Trans. from English - M .: Publishing house "Williams", 2002.
MN Vyalyy, The complexity of computational problems - the definition of functions, without the concepts of "language", "alphabet", etc.

Karp Information

Transitivity

See also

Links

More articles: