No sākuma atgādināsim tās definīcijas, kas tiek pieminētas iepriekšēja lekcijā:

Instance: A graph G = (V, E) and a positive integer K<= |V|

Question: Is there a vertex cover of size K or less for G, that is a subset V’ī V such that |V’| <= K and for each edge (u,v) ļ E, at least one of u and V belogs to V’

Instance: A graph G = (V, E)

Question: Does G contain a Hamiltonian circuit, that is an ordering < v₁, v₂, … , v_n > of the vertices of G, where n = |V| such that { v_n, v₁ } ļ E and { v_i, v_i+1 } ļ E for all i,

1 <= i <= n.

Tagad apskatīsim sekojošu teorēmu:

Mums vajag katram virsotņu pārklājumam uzkonstruēt atbilstošu grafu, kurā norādīt Hamiltona ciklu.

Katrai šķautnei e = (u,v) dotajā grafā atbilst bloks.

Kur v un u ir virsotnes, kuras savieno šī šķautne. Šinī grafa virsotnes (u,e,1), (v,e,1), (u,e,6) un (v,e,6) ir saistītas ar ārpusi.

Katrai virsotnei v dotajā grafā kaut kā ir sanumurētas šķautnes, kas ieiet (iziet) šajā virsotnē e_1, e₂, … , e_d . Tas nozēme, ka katra virsotne ir d blokos. Bloki ir savienoti un pedējais bloks ir savienots ar pirmo (skat. 4.zīm.). Bez šiem blokiem, jaunajā grafā ir vēl k virsotnes a₁, a₂, … , a_k, kuras sauc par selektora virsotnēm. Kur k ir no VC definīcijas (virsotņu skaits pārklājumā).

Ja dotajā grafā ir pārklājums ar izmēru k, tad a₁, a₂, … , a_k asociē ar virsotnēm pārklājumā (v₁, v₂, … , v).

Šajā grafā (skat. 4.zīm.) eksistē Hamiltona cikls. Katru bloku mēs apstaigājam, kā ir uzradīts zīmējumos 1), 2), 3). Sākot no virsotnes a₁, apstaigājot visus pirmas virsotnes blokus, mēs atgriežamies virsotnē a₂ u tt. var apstaigāt visas virsotnes un atgriezties virsotnā a₁.

Talāk tiek apskatīti dažādi NP-pilni uzdevumi visi ir poly reducējami viens uz otru:

Instance: Collection C of subsets of a finite set S, positive integer K<= Ė C Ė

Question: Does C contain ir cover for S of size K or less, i.e. a subset C '= C with

Ė C ' Ė <= K such that every element of S belongs to at least one member of C '

Instance: Finite set A, size S(a) ļ Z⁺ for each a ļ A, positive integer B.

Question: Is there a subset A'<= A such that the sum of sizes of the elements in A' ie exactly B.

Instance: Finite set U of items, a size S(u) ļ Z⁺ for each uļ U a positive integer bin capacity, and a positive integer K.

Question: Is there a partition of U into disjoint sets u₁,u₂, … , u_k such that the sum of sizes of the items in each u_i is B or less.

Instance: Finite alfabet å , finite set R of strings from å ^* and a positive integer K.

Question: Is there a string w ļ Å ^* with Ė w Ė <= K such that each string xļ R is a subsequence of w, i.e.

w = w₀ x₁w₁ x₂w₂…x_kw_k, where each w_i ļ Å ^* and x = x₁x₂…x_k

k <= m*n

Question: Is there a sequence (b₁,b₂, … ,b_n+k) of integers b each satisfying 0<= b_i <= m and a function.

S: {1, 2, … , m}® {1, 2, … , K} such that, for 1<= i <= m and 1 <= j <= n, the entry a_ij = 1 if and only if b_{S(i)+ j-1}= I

Instance: Finite alphabet Å , two strings x,y ļ Å ^*, and a positive integer K

Question: Is there a way to derive the string y from the string x by a sequence of k or fewer operations of single symbol deletion or adjacent symbol interchange.