NP-Hard ΠΡΠΎΠ±Π»Π΅ΠΌΠ°
"ΠΠ°Π½ΠΎ ΡΠΏΠΈΡΠΎΠΊ ΠΌΡΡΡ. Π―ΠΊΠΈΠΉ Π½Π°ΠΉΠΊΠΎΡΠΎΡΡΠΈΠΉ ΡΠ»ΡΡ , ΡΠΎΠ± Π²ΡΠ΄Π²ΡΠ΄Π°ΡΠΈ ΠΊΠΎΠΆΠ½Π΅ ΠΌΡΡΡΠΎ ΡΡΠ²Π½ΠΎ ΠΎΠ΄ΠΈΠ½ ΡΠ°Π· Ρ ΠΏΠΎΠ²Π΅ΡΠ½ΡΡΠΈΡΡ Π½Π°Π·Π°Π΄?"
Π§ΠΎΠΌΡ ΡΠ΅ Π²Π°ΠΆΠΊΠΎ?
ΠΠ»Ρ N ΠΌΡΡΡ ΡΡΠ½ΡΡ
β’ 10 ΠΌΡΡΡ: ~181 ΡΠΈΡΡΡΠ° ΡΠ»ΡΡ ΡΠ².
β’ 20 ΠΌΡΡΡ: ~6 Γ 10ΒΉβΆ (60 ΠΊΠ²Π°Π΄ΡΠΈΠ»ΡΠΉΠΎΠ½ΡΠ²).
ΠΠ»Ρ N ΠΌΡΡΡ ΡΡΠ½ΡΡ
(N-1)! / 2 ΠΌΠΎΠΆΠ»ΠΈΠ²ΠΈΡ
ΠΌΠ°ΡΡΡΡΡΡΠ².
β’ 10 ΠΌΡΡΡ: ~181 ΡΠΈΡΡΡΠ° ΡΠ»ΡΡ ΡΠ².
β’ 20 ΠΌΡΡΡ: ~6 Γ 10ΒΉβΆ (60 ΠΊΠ²Π°Π΄ΡΠΈΠ»ΡΠΉΠΎΠ½ΡΠ²).
ΠΠΈ Π½Π΅ ΠΌΠΎΠΆΠ΅ΠΌΠΎ ΠΏΠ΅ΡΠ΅Π²ΡΡΠΈΡΠΈ Π²ΡΡ. Π’ΠΎΠΌΡ Π²ΠΈΠΊΠΎΡΠΈΡΡΠΎΠ²ΡΡΠΌΠΎ Π΅Π²ΡΠΈΡΡΠΈΠΊΠΈ (Π½Π°Π±Π»ΠΈΠΆΠ΅Π½Ρ ΠΌΠ΅ΡΠΎΠ΄ΠΈ), ΡΠ°ΠΊΡ ΡΠΊ Π²ΠΈΠΏΠ°Π΄ΠΊΠΎΠ²Ρ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ Π°Π±ΠΎ ΠΠ΅Π½Π΅ΡΠΈΡΠ½Ρ ΠΠ»Π³ΠΎΡΠΈΡΠΌΠΈ, ΡΠΎΠ± Π·Π½Π°ΠΉΡΠΈ "Π΄ΠΎΡΡΠ°ΡΠ½ΡΠΎ Π³Π°ΡΠ½ΠΈΠΉ" ΡΠΎΠ·Π²'ΡΠ·ΠΎΠΊ.
ΠΡΡΡ: 20
0