yazan: Şadi Evren ŞEKER
Algoritma teorisinde meşhur problemlerden birisidir. NP-Complete problemlere iyi bir örnektir. Problemin tanımı aşağıdaki şekildedir:
verilen eksi ve artı tam sayılar kümesinin herhangi bir alt kümesinin toplamının 0 olduğunu bulmak.
Bu problemin kontrol edilmesi oldukça basittir ancak verilen sayı kümesinden yukarıdaki tanımı sağlayan bir alt küme bulmak kolay değildir.
Problemin örnek çözümü:
verilen sayı kümesi : { 1,4,-5,2,7,-4,2,9} olsun. Bu sayı kümesinin öyle bir alt kümesi var mıdır ki toplamı 0 olsun?
evet böyle bir alt küme buluna bilir örnek:
{-4,4} veya {-4,2,2} veya {1,4,-5} veya {9,-4,-5} … gibi
yukarıdaki örnek için bütün çözümleri verecek bir yöntemin geliştirilmesi mümkün olsa bile bu yöntemin çalışmas süresi problem kümesi büyüdükçe çok çok yüksek değerlere çıkacaktır.
daha fazla bilgi için.
NP-Complete
NP-Hard
tanımlarına bakabilirsiniz.
[...] NP kümesinde bulunan başka bir probleme dönüştürmektir. En meşhur problemlerden bazıları: Altküme toplam problemi RSA [...]
[...] mesaja saldırmak isteyen kişinin uğraşması gereken zorluk alt küme toplam problemi zorluğudur çünkü saldıran kişi B değerlerini bilmemektedir ve tahmin etmesinin tek yolu [...]