ΠΠ²Π΅Π΄Π΅Π½ΠΈΠ΅.
ΠΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅.
ΠΠ°Π΄Π°ΡΠ° ΠΎ Π·Π°Π³ΡΡΠ·ΠΊΠ΅
Π Π°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°Π΅ΠΌΠ°Ρ Π½Π°ΠΌΠΈ Π·Π°Π΄Π°ΡΠ° ΡΠ²Π»ΡΠ΅ΡΡΡ NP — ΠΏΠΎΠ»Π½ΠΎΠΉ, ΡΠΎ Π΅ΡΡΡ Π΄Π»Ρ Π½Π΅Π΅ Π½Π΅ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΈΠ°Π»ΡΠ½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°, ΡΠ΅ΡΠ°ΡΡΠ΅Π³ΠΎ Π΅Ρ Π·Π° ΡΠ°Π·ΡΠΌΠ½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ, Π² ΡΡΠΎΠΌ ΠΈ Π΅ΡΡΡ ΠΏΡΠΎΠ±Π»Π΅ΠΌΠ°. ΠΠΈΠ±ΠΎ ΠΌΡ Π²ΡΠ±ΠΈΡΠ°Π΅ΠΌ Π±ΡΡΡΡΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ, Π½ΠΎ ΠΎΠ½ ΠΊΠ°ΠΊ ΠΈΠ·Π²Π΅ΡΡΠ½ΠΎ Π½Π΅ Π²ΡΠ΅Π³Π΄Π° ΡΠ΅ΡΠ°Π΅Ρ Π·Π°Π΄Π°ΡΡ Π½Π°ΠΈΠ»ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, Π»ΠΈΠ±ΠΎ Π²ΡΠ±ΠΈΡΠ°Π΅ΠΌ ΡΠΎΡΠ½ΡΠΉ, ΠΊΠΎΡΠΎΡΡΠΉ ΠΎΠΏΡΡΡ ΠΆΠ΅ Π½Π΅ ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠ°Π±ΠΎΡΠΎΡΠΏΠΎΡΠΎΠ±Π½ΡΠΌ Π΄Π»Ρ Π±ΠΎΠ»ΡΡΠΈΡ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ. Π‘ΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ ΠΌΠΎΠ΄ΠΈΡΠΈΠΊΠ°ΡΠΈΠΉ Π·Π°Π΄Π°ΡΠΈ. ΠΡΠ»ΠΈ ΠΆΠ΅… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
ΠΠ²Π΅Π΄Π΅Π½ΠΈΠ΅. ΠΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅. ΠΠ°Π΄Π°ΡΠ° ΠΎ Π·Π°Π³ΡΡΠ·ΠΊΠ΅ (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
ΠΠ»Π°ΡΡΠΈΡΠ΅ΡΠΊΠ°Ρ Π·Π°Π΄Π°ΡΠ° ΠΎ ΡΡΠΊΠ·Π°ΠΊΠ΅ (ΠΎ Π·Π°Π³ΡΡΠ·ΠΊΠ΅) ΠΈΠ·Π²Π΅ΡΡΠ½Π° ΠΎΡΠ΅Π½Ρ Π΄Π°Π²Π½ΠΎ, Π½ΠΈΠΆΠ΅ ΠΏΡΠΈΠ²Π΅Π΄Π΅Π½Π° Π΅Π΅ ΡΠΎΡΠΌΠ°Π»ΠΈΠ·Π°ΡΠΈΡ. ΠΡΡΡΡ Π΅ΡΡΡ N ΡΠ°Π·Π½ΡΡ ΠΏΡΠ΅Π΄ΠΌΠ΅ΡΠΎΠ², ΠΊΠ°ΠΆΠ΄ΡΠΉ ΠΏΡΠ΅Π΄ΠΌΠ΅Ρ ΠΈΠΌΠ΅Π΅Ρ Π²Π΅Ρ wi ΠΈ ΠΏΠΎΠ»Π΅Π·Π½ΠΎΡΡΡ pi, ΡΠ°ΠΊ ΠΆΠ΅ ΠΈΠΌΠ΅Π΅ΡΡΡ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ Π²Π΅Ρ W, ΠΊΠΎΡΠΎΡΡΠΉ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΠ»ΠΎΠΆΠΈΡΡ Π² ΡΡΠΊΠ·Π°ΠΊ. Π’ΡΠ΅Π±ΡΠ΅ΡΡΡ ΡΠΎΠ±ΡΠ°ΡΡ ΡΠ°ΠΊΠΎΠΉ Π½Π°Π±ΠΎΡ ΠΏΡΠ΅Π΄ΠΌΠ΅ΡΠΎΠ² P, ΡΡΠΎΠ±Ρ ΠΏΠΎΠ»Π΅Π·Π½ΠΎΡΡΡ ΠΈΡ Π±ΡΠ»Π° Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠ΅ΠΉ, Π° ΡΡΠΌΠΌΠ°ΡΠ½ΡΠΉ Π²Π΅Ρ Π½Π΅ ΠΏΡΠ΅Π²ΡΡΠ°Π» W. ΠΠΎΠ½Π΅ΡΠ½ΠΎ, Π½ΠΈΠΊΡΠΎ Π½Π΅ ΡΠΎΠ±ΠΈΡΠ°Π΅ΡΡΡ ΠΏΠΈΡΠ°ΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ, ΡΡΠΎΠ±Ρ Π½Π°ΠΈΠ»ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ Π·Π°Π³ΡΡΠ·ΠΈΡΡ ΡΡΠΊΠ·Π°ΠΊ, ΠΎΡΠΏΡΠ°Π²Π»ΡΡΡΡ Π² ΠΏΠΎΡ ΠΎΠ΄ ΠΈΠ»ΠΈ Π² ΠΏΡΡΠ΅ΡΠ΅ΡΡΠ²ΠΈΠ΅, ΡΡΡ Π²ΡΠ΅ ΡΠ»ΠΈΡΠΊΠΎΠΌ ΠΏΡΠΎΡΡΠΎ, ΠΈ Π½ΠΈΠΊΡΠΎ Π½Π΅ Π·Π°Π΄ΡΠΌΡΠ²Π°Π΅ΡΡΡ ΠΎΠ± ΡΡΠΎΠΌ, Π½ΠΎ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ ΠΈ Π±ΠΎΠ»Π΅Π΅ ΡΠΈΡΠΎΠΊΠΎΠ΅ ΠΏΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅.
ΠΠ°Π΄Π°ΡΠ° ΠΎ Π·Π°Π³ΡΡΠ·ΠΊΠ΅ (Π·Π°Π΄Π°ΡΠ° ΠΎ ΡΡΠΊΠ·Π°ΠΊΠ΅) ΠΈ ΡΠ°Π·Π»ΠΈΡΠ½ΡΠ΅ Π΅Ρ ΠΌΠΎΠ΄ΠΈΡΠΈΠΊΠ°ΡΠΈΠΈ ΡΠΈΡΠΎΠΊΠΎ ΠΏΡΠΈΠΌΠ΅Π½ΡΡΡΡΡ Π½Π° ΠΏΡΠ°ΠΊΡΠΈΠΊΠ΅ Π² ΠΏΡΠΈΠΊΠ»Π°Π΄Π½ΠΎΠΉ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠ΅, ΠΊΡΠΈΠΏΡΠΎΠ³ΡΠ°ΡΠΈΠΈ, ΡΠΊΠΎΠ½ΠΎΠΌΠΈΠΊΠ΅, Π»ΠΎΠ³ΠΈΡΡΠΈΠΊΠ΅, Π΄Π»Ρ Π½Π°Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΡ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΉ Π·Π°Π³ΡΡΠ·ΠΊΠΈ ΡΠ°Π·Π»ΠΈΡΠ½ΡΡ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΡΡ ΡΡΠ΅Π΄ΡΡΠ²: ΡΠ°ΠΌΠΎΠ»Π΅ΡΠΎΠ², ΠΊΠΎΡΠ°Π±Π»Π΅ΠΉ, ΠΆΠ΅Π»Π΅Π·Π½ΠΎΠ΄ΠΎΡΠΎΠΆΠ½ΡΡ Π²Π°Π³ΠΎΠ½ΠΎΠ² ΠΈ Ρ. Π΄.
Π Π°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°Π΅ΠΌΠ°Ρ Π½Π°ΠΌΠΈ Π·Π°Π΄Π°ΡΠ° ΡΠ²Π»ΡΠ΅ΡΡΡ NP — ΠΏΠΎΠ»Π½ΠΎΠΉ, ΡΠΎ Π΅ΡΡΡ Π΄Π»Ρ Π½Π΅Π΅ Π½Π΅ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΈΠ°Π»ΡΠ½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°, ΡΠ΅ΡΠ°ΡΡΠ΅Π³ΠΎ Π΅Ρ Π·Π° ΡΠ°Π·ΡΠΌΠ½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ, Π² ΡΡΠΎΠΌ ΠΈ Π΅ΡΡΡ ΠΏΡΠΎΠ±Π»Π΅ΠΌΠ°. ΠΠΈΠ±ΠΎ ΠΌΡ Π²ΡΠ±ΠΈΡΠ°Π΅ΠΌ Π±ΡΡΡΡΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ, Π½ΠΎ ΠΎΠ½ ΠΊΠ°ΠΊ ΠΈΠ·Π²Π΅ΡΡΠ½ΠΎ Π½Π΅ Π²ΡΠ΅Π³Π΄Π° ΡΠ΅ΡΠ°Π΅Ρ Π·Π°Π΄Π°ΡΡ Π½Π°ΠΈΠ»ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, Π»ΠΈΠ±ΠΎ Π²ΡΠ±ΠΈΡΠ°Π΅ΠΌ ΡΠΎΡΠ½ΡΠΉ, ΠΊΠΎΡΠΎΡΡΠΉ ΠΎΠΏΡΡΡ ΠΆΠ΅ Π½Π΅ ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠ°Π±ΠΎΡΠΎΡΠΏΠΎΡΠΎΠ±Π½ΡΠΌ Π΄Π»Ρ Π±ΠΎΠ»ΡΡΠΈΡ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ. Π‘ΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ ΠΌΠΎΠ΄ΠΈΡΠΈΠΊΠ°ΡΠΈΠΉ Π·Π°Π΄Π°ΡΠΈ.
- 1) ΠΠ°ΠΆΠ΄ΡΠΉ ΠΏΡΠ΅Π΄ΠΌΠ΅Ρ ΠΌΠΎΠΆΠ½ΠΎ Π±ΡΠ°ΡΡ ΡΠΎΠ»ΡΠΊΠΎ ΠΎΠ΄ΠΈΠ½ ΡΠ°Π·.
- 2) ΠΠ°ΠΆΠ΄ΡΠΉ ΠΏΡΠ΅Π΄ΠΌΠ΅Ρ ΠΌΠΎΠΆΠ½ΠΎ Π±ΡΠ°ΡΡ ΡΠΊΠΎΠ»ΡΠΊΠΎ ΡΠ³ΠΎΠ΄Π½ΠΎ ΡΠ°Π·.
- 3) ΠΠ°ΠΆΠ΄ΡΠΉ ΠΏΡΠ΅Π΄ΠΌΠ΅Ρ ΠΌΠΎΠΆΠ½ΠΎ Π±ΡΠ°ΡΡ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ°Π·
- 4) ΠΠ° ΡΠ°Π·ΠΌΠ΅Ρ ΡΡΠΊΠ·Π°ΠΊΠ° ΠΈΠΌΠ΅Π΅ΡΡΡ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½ΠΈΠΉ.
- 5) ΠΠ΅ΠΊΠΎΡΠΎΡΡΠ΅ Π²Π΅ΡΠΈ ΠΈΠΌΠ΅Ρ Π±ΠΎΠ»ΡΡΠΈΠΉ ΠΏΡΠΈΠΎΡΠΈΡΠ΅Ρ, ΡΠ΅ΠΌ Π΄ΡΡΠ³ΠΈΠ΅
Π¦Π΅Π»Ρ Π΄Π°Π½Π½ΠΎΠΉ ΡΠ°Π±ΠΎΡΡ — ΠΎΠΏΠΈΡΠ°ΡΡ ΠΌΠ΅ΡΠΎΠ΄ Π·Π°Π΄Π°ΡΠΈ ΠΎ Π·Π°Π³ΡΡΠ·ΠΊΠ΅ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ.
ΠΡΠ½ΠΎΠ²Π½ΠΎΠΉ Π·Π°Π΄Π°ΡΠ΅ΠΉ ΠΊΡΡΡΠΎΠ²ΠΎΠ³ΠΎ ΠΏΡΠΎΠ΅ΠΊΡΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠ΅Π°Π»ΠΈΠ·ΠΎΠ²Π°ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΠΊΠ»Π°ΡΡΠΈΡΠ΅ΡΠΊΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ ΠΎ ΡΡΠΊΠ·Π°ΠΊΠ΅ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ.
ΠΠΎΡΡΠ°Π½ΠΎΠ²ΠΊΠ° Π·Π°Π΄Π°ΡΠΈ ΠΎ ΡΡΠΊΠ·Π°ΠΊΠ΅.
ΠΠ°Π΄Π°ΡΠ° ΠΎ ΡΠ°Π½ΡΠ΅ — ΠΎΠ΄Π½Π° ΠΈΠ· Π·Π°Π΄Π°Ρ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΎΡΠ½ΠΎΠΉ ΠΎΠΏΡΠΈΠΌΠΈΠ·Π°ΡΠΈΠΈ. ΠΠ»Π°ΡΡΠΈΡΠ΅ΡΠΊΠ°Ρ Π·Π°Π΄Π°ΡΠ° ΠΎ ΡΠ°Π½ΡΠ΅ ΠΈΠ·Π²Π΅ΡΡΠ½Π° ΠΎΡΠ΅Π½Ρ Π΄Π°Π²Π½ΠΎ. ΠΠΎΡ Π΅Ρ ΠΏΠΎΡΡΠ°Π½ΠΎΠ²ΠΊΠ°: ΠΠΌΠ΅Π΅ΡΡΡ Π½Π°Π±ΠΎΡ ΠΈΠ· N ΠΏΡΠ΅Π΄ΠΌΠ΅ΡΠΎΠ², ΠΊΠ°ΠΆΠ΄ΡΠΉ ΠΏΡΠ΅Π΄ΠΌΠ΅Ρ ΠΈΠΌΠ΅Π΅Ρ ΠΌΠ°ΡΡΡ Wi ΠΈ ΠΏΠΎΠ»Π΅Π·Π½ΠΎΡΡΡ Vi, i=(1,2.N), ΡΡΠ΅Π±ΡΠ΅ΡΡΡ ΡΠΎΠ±ΡΠ°ΡΡ Π½Π°Π±ΠΎΡ Ρ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΉ ΠΏΠΎΠ»Π΅Π·Π½ΠΎΡΡΡΡ ΡΠ°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΡΡΠΎΠ±Ρ ΠΎΠ½ ΠΈΠΌΠ΅Π» Π²Π΅Ρ Π½Π΅ Π±ΠΎΠ»ΡΡΠ΅ W, Π³Π΄Π΅ W — Π²ΠΌΠ΅ΡΡΠΈΠΌΠΎΡΡΡ ΡΠ°Π½ΡΠ°. Π’ΡΠ°Π΄ΠΈΡΠΈΠΎΠ½Π½ΠΎ ΠΏΠΎΠ»Π°Π³Π°ΡΡ ΡΡΠΎ Wi, Vi, W, P — ΡΠ΅Π»ΡΠ΅ Π½Π΅ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½ΡΠ΅ ΡΠΈΡΠ»Π°, Π½ΠΎ Π²ΡΡΡΠ΅ΡΠ°ΡΡΡΡ ΠΈ Π΄ΡΡΠ³ΠΈΠ΅ ΠΏΠΎΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ, ΡΡΠ»ΠΎΠ²ΠΈΡ Π² ΠΊΠΎΡΠΎΡΡΡ ΠΌΠΎΠ³ΡΡ ΠΎΡΠ»ΠΈΡΠ°ΡΡΡΡ. ΠΠΎΠ·ΠΌΠΎΠΆΠ½Ρ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ Π²Π°ΡΠΈΠ°ΡΠΈΠΈ Π·Π°Π΄Π°ΡΠΈ:
ΠΠ°ΠΆΠ΄ΡΠΉ ΠΏΡΠ΅Π΄ΠΌΠ΅Ρ ΠΌΠΎΠΆΠ½ΠΎ Π±ΡΠ°ΡΡ ΡΠΎΠ»ΡΠΊΠΎ ΠΎΠ΄ΠΈΠ½ ΡΠ°Π·. Π€ΠΎΡΠΌΠ°Π»ΠΈΠ·ΡΠ΅ΠΌ.
ΠΡΡΡΡ Π·Π°Π΄Π°Π½ΠΎ ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΠΏΡΠ΅Π΄ΠΌΠ΅ΡΠΎΠ², Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ, ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π° ΡΡΠΎΠΈΠΌΠΎΡΡΡ pi ΠΈ Π²Π΅Ρ wi, ΡΠΎΠ³Π΄Π° Π½ΡΠΆΠ½ΠΎ ΠΌΠ°ΠΊΡΠΈΠΌΠΈΠ·ΠΈΡΠΎΠ²Π°ΡΡ.
ΠΏΡΠΈ ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½ΠΈΡΡ .
Π³Π΄Π΅ W-Π²ΠΌΠ΅ΡΡΠΈΠΌΠΎΡΡΡ ΡΠ°Π½ΡΠ°, Π° xi=1, Π΅ΡΠ»ΠΈ ΠΏΡΠ΅Π΄ΠΌΠ΅Ρ Π²Π·ΡΡ Π΄Π»Ρ Π·Π°Π³ΡΡΠ·ΠΊΠΈ ΠΈ xi=0 Π΅ΡΠ»ΠΈ Π½Π΅ Π²Π·ΡΡ. ΠΡΠ»ΠΈ Π½Π° ΡΠ°Π·ΠΌΠ΅Ρ ΡΡΠΊΠ·Π°ΠΊΠ° ΠΈΠΌΠ΅Π΅ΡΡΡ ΡΠΎΠ»ΡΠΊΠΎ ΠΎΠ΄Π½ΠΎ ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½ΠΈΠ΅, ΡΠΎ Π·Π°Π΄Π°ΡΠ° Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΎΠ΄Π½ΠΎΠΌΠ΅ΡΠ½ΠΎΠΉ, Π² ΠΏΡΠΎΡΠΈΠ²Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ — ΠΌΠ½ΠΎΠ³ΠΎΠΌΠ΅ΡΠ½ΠΎΠΉ.
ΠΠ°ΠΆΠ΄ΡΠΉ ΠΏΡΠ΅Π΄ΠΌΠ΅Ρ ΠΌΠΎΠΆΠ½ΠΎ Π±ΡΠ°ΡΡ m ΡΠ°Π·. Π€ΠΎΡΠΌΠ°Π»ΠΈΠ·Π°ΡΠΈΡ Π°Π½Π°Π»ΠΎΠ³ΠΈΡΠ½Π°, ΡΠ°Π·Π½ΠΈΡΠ° Π»ΠΈΡΡ Π² ΡΠΎΠΌ, ΡΡΠΎ xi ΠΏΡΠΈΠ½ΠΈΠΌΠ°Π΅Ρ Π·Π½Π°ΡΠ΅Π½ΠΈΡ Π½Π° ΠΈΠ½ΡΠ΅ΡΠ²Π°Π»Π΅ (0.m).
ΠΠ°ΠΆΠ΄ΡΠΉ ΠΏΡΠ΅Π΄ΠΌΠ΅Ρ ΠΌΠΎΠΆΠ½ΠΎ Π±ΡΠ°ΡΡ Π½Π΅ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½Π½ΠΎΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ°Π·. ΠΡΠ΅Π²ΠΈΠ΄Π½ΠΎ, ΡΡΠΎ xi Π»Π΅ΠΆΠΈΡ Π² Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½Π΅ (0. W/wi]) ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΡΠ΅ ΡΠΊΠΎΠ±ΠΎΡΠΊΠΈ ΠΎΠ·Π½Π°ΡΠ°ΡΡ ΡΠ΅Π»ΡΡ ΡΠ°ΡΡΡ ΡΠΈΡΠ»Π°.
ΠΡΠ»ΠΈ ΠΆΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΡ Π²Π΅ΡΠΎΠ² ΠΈ ΡΠ΅Π½ ΠΏΡΠ΅Π΄ΠΌΠ΅ΡΠΎΠ² Π½Π΅ ΡΠ΅Π»ΡΠ΅ ΡΠΈΡΠ»Π°, ΡΠ°ΠΊΠ°Ρ Π·Π°Π΄Π°ΡΠ° Π±ΡΠ΄Π΅Ρ Π½Π°Π·ΡΠ²Π°ΡΡΡΡ Π½Π΅ΠΏΡΠ΅ΡΡΠ²Π½ΠΎΠΉ Π·Π°Π΄Π°ΡΠ΅ΠΉ ΠΎ ΡΡΠΊΠ·Π°ΠΊΠ΅, Π΅ΡΠ»ΠΈ ΠΆΠ΅ ΡΠΈΡΠ»Π° ΡΠ΅Π»ΡΠ΅, ΡΠΎ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²Π΅Π½Π½ΠΎ Π΄ΠΈΡΠΊΡΠ΅ΡΠ½ΠΎΠΉ. ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, Π΅ΡΠ»ΠΈ ΠΌΡ ΠΈΠΌΠ΅Π΅ΠΌ Π΄Π΅Π»ΠΎ Ρ Π·ΠΎΠ»ΠΎΡΡΠΌΠΈ ΡΠ»ΠΈΡΠΊΠ°ΠΌΠΈ, ΠΌΡ Π½Π΅ ΠΌΠΎΠΆΠ΅ΠΌ ΠΈΡ Π΄Π΅Π»ΠΈΡΡ — ΡΡΠΎ Π΄ΠΈΡΠΊΡΠ΅ΡΠ½Π°Ρ Π·Π°Π΄Π°ΡΠ°, Π° Π΅ΡΠ»ΠΈ Ρ Π·ΠΎΠ»ΠΎΡΡΠΌ ΠΏΠ΅ΡΠΊΠΎΠΌ, ΡΠΎ ΡΡΠΎ Π½Π΅ΠΏΡΠ΅ΡΡΠ²Π½Π°Ρ Π·Π°Π΄Π°ΡΠ° ΠΎ ΡΡΠΊΠ·Π°ΠΊΠ΅.
NP — ΠΏΠΎΠ»Π½ΠΎΡΠ° Π·Π°Π΄Π°ΡΠΈ.
ΠΠΎΠ»ΡΡΠΈΠ½ΡΡΠ²ΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΠΈΠΌΠ΅ΡΡ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΈΠ°Π»ΡΠ½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ, Π΅ΡΠ»ΠΈ ΡΠ°Π·ΠΌΠ΅Ρ Π²Ρ ΠΎΠ΄Π½ΡΡ Π΄Π°Π½Π½ΡΡ — n, ΡΠΎ Π²ΡΠ΅ΠΌΡ ΠΈΡ ΡΠ°Π±ΠΎΡΡ Π² Ρ ΡΠ΄ΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ ΠΎΡΠ΅Π½ΠΈΠ²Π°Π΅ΡΡΡ ΠΊΠ°ΠΊ.
Π³Π΄Π΅ k ΡΡΠΎ ΠΊΠΎΠ½ΡΡΠ°Π½ΡΠ°. ΠΠΎ Π²ΡΡΡΠ΅ΡΠ°ΡΡΡΡ Π·Π°Π΄Π°ΡΠΈ, ΠΊΠΎΡΠΎΡΡΠ΅ Π½Π΅Π»ΡΠ·Ρ ΡΠ°Π·ΡΠ΅ΡΠΈΡΡ Π·Π° ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΈΠ°Π»ΡΠ½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ. ΠΡΠΎ ΠΊΠ»Π°ΡΡ NP — ΠΏΠΎΠ»Π½ΡΡ Π·Π°Π΄Π°Ρ. ΠΠ΅ΠΊΠΎΡΠΎΡΡΠ΅ Π·Π°Π΄Π°ΡΠΈ ΡΡΠΎΠ³ΠΎ ΠΊΠ»Π°ΡΡΠ° Π½Π° ΠΏΠ΅ΡΠ²ΡΠΉ Π²Π·Π³Π»ΡΠ΄ Π°Π½Π°Π»ΠΎΠ³ΠΈΡΠ½Ρ Π·Π°Π΄Π°ΡΠ°ΠΌ ΡΠ°Π·ΡΠ΅ΡΠΈΠΌΡΠΌ Π·Π° ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΈΠ°Π»ΡΠ½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ, Π½ΠΎ ΡΡΠΎ Π΄Π°Π»Π΅ΠΊΠΎ Π½Π΅ ΡΠ°ΠΊ. ΠΠ°Π΄Π°ΡΠ° Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ NP — ΠΏΠΎΠ»Π½ΠΎΠΉ, Π΅ΡΠ»ΠΈ Π΄Π»Ρ Π½Π΅Π΅ Π½Π΅ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΈΠ°Π»ΡΠ½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°. ΠΠ»Π³ΠΎΡΠΈΡΠΌ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΈΠ°Π»ΡΠ½ΡΠΌ, Π΅ΡΠ»ΠΈ Π΅Π³ΠΎ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ O (N) Π² Ρ ΡΠ΄ΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½Π° ΡΠ²Π΅ΡΡ Ρ Π½Π΅ΠΊΠΎΡΠΎΡΡΠΌ ΠΌΠ½ΠΎΠ³ΠΎΡΠ»Π΅Π½ΠΎΠΌ (ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΎΠΌ) ΠΎΡ N. Π’Π°ΠΊΠΈΠ΅ Π·Π°Π΄Π°ΡΠΈ Π²ΠΎΠ·Π½ΠΈΠΊΠ°ΡΡ ΠΎΡΠ΅Π½Ρ ΡΠ°ΡΡΠΎ Π² ΡΠ°Π·Π»ΠΈΡΠ½ΡΡ ΠΎΠ±Π»Π°ΡΡΡΡ : Π² Π±ΡΠ»Π΅Π²ΠΎΠΉ Π»ΠΎΠ³ΠΈΠΊΠ΅, Π² ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ², ΡΠ΅ΠΎΡΠΈΠΈ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ², ΠΊΠΎΠ΄ΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ, Π² Π°Π»Π³Π΅Π±ΡΠ΅, Π² Π±ΠΈΠΎΠ»ΠΎΠ³ΠΈΠΈ, ΡΠΈΠ·ΠΈΠΊΠ΅, ΡΠΊΠΎΠ½ΠΎΠΌΠΈΠΊΠ΅, ΡΠ΅ΠΎΡΠΈΠΈ Π°Π²ΡΠΎΠΌΠ°ΡΠΎΠ² ΠΈ ΡΠ·ΡΠΊΠΎΠ². Π‘ΡΠΈΡΠ°Π΅ΡΡΡ ΡΡΠΎ NP — ΠΏΠΎΠ»Π½ΡΠ΅ Π·Π°Π΄Π°ΡΠΈ ΠΎΡΠ΅Π½Ρ ΡΡΡΠ΄Π½ΠΎΡΠ°Π·ΡΠ΅ΡΠΈΠΌΡ, Π° ΡΠ°ΠΊ ΠΆΠ΅, ΡΡΠΎ Π΅ΡΠ»ΠΈ Ρ ΠΎΡΡ Π±Ρ Π΄Π»Ρ ΠΎΠ΄Π½ΠΎΠΉ ΠΈΠ· Π½ΠΈΡ ΡΠ΄Π°ΡΡΡΡ Π½Π°ΠΉΡΠΈ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΈΠ°Π»ΡΠ½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ, ΡΠΎ ΡΠ°ΠΊΠΎΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ Π±ΡΠ΄Π΅Ρ ΡΡΡΠ΅ΡΡΠ²ΠΎΠ²Π°ΡΡ Π΄Π»Ρ Π»ΡΠ±ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ ΠΈΠ· ΡΡΠΎΠ³ΠΎ ΠΊΠ»Π°ΡΡΠ°.
ΠΠ°Π΄ ΠΏΠΎΠΈΡΠΊΠΎΠΌ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΈΠ°Π»ΡΠ½ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΠΊ ΡΠ°ΠΊΠΈΠΌ Π·Π°Π΄Π°ΡΠ°ΠΌ ΡΡΡΠ΄ΠΈΠ»ΠΈΡΡ ΠΌΠ½ΠΎΠ³ΠΈΠ΅ ΡΡΠ΅Π½ΡΠ΅, ΠΈ Π²ΡΠ΅ ΠΆΠ΅ ΠΈ Π²ΡΠ΅ ΠΆΠ΅ ΠΏΡΠΈ ΡΠ°ΠΊΠΎΠΌ ΡΠ°Π·Π½ΠΎΠΎΠ±ΡΠ°Π·ΠΈΠΈ NP — ΠΏΠΎΠ»Π½ΡΡ Π·Π°Π΄Π°Ρ, Π½ΠΈ Π΄Π»Ρ ΠΎΠ΄Π½ΠΎΠΉ ΠΈΠ· Π½ΠΈΡ Π΄ΠΎ ΡΠΈΡ ΠΏΠΎΡ Π½Π΅ Π½Π°ΠΉΠ΄Π΅Π½ΠΎ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΈΠ°Π»ΡΠ½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°.
ΠΠ· Π²ΡΠ΅Π³ΠΎ Π²ΡΡΠ΅ΡΠΊΠ°Π·Π°Π½Π½ΠΎΠ³ΠΎ ΡΠ»Π΅Π΄ΡΠ΅Ρ, ΡΡΠΎ Π΅ΡΠ»ΠΈ ΠΈΠ·Π²Π΅ΡΡΠ½Π° NP — ΠΏΠΎΠ»Π½ΠΎΡΠ° Π·Π°Π΄Π°ΡΠΈ, ΡΠΎ Π»ΡΡΡΠ΅ ΠΏΠΎΡΡΠ°ΡΠΈΡΡ Π²ΡΠ΅ΠΌΡ Π½Π° ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΠ΅ ΠΏΡΠΈΠ±Π»ΠΈΠΆΠ΅Π½Π½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°, ΡΠ΅ΠΌ ΠΏΡΡΠ°ΡΡΡΡ ΠΏΠΎΡΡΡΠΎΠΈΡΡ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΈΠ°Π»ΡΠ½ΡΠΉ, ΠΈΠ»ΠΈ ΠΆΠ΅, Π΅ΡΠ»ΠΈ ΡΡΠΎ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡΡ ΡΡΠ»ΠΎΠ²ΠΈΡ, ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ Ρ ΡΠΊΡΠΏΠΎΠ½Π΅Π½ΡΠΈΠ°Π»ΡΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡΡ ΡΠ°Π±ΠΎΡΡ.