P versus NP problemi, 1971 yılında Stephen Cook ve Leonid Levin adlı matematikçiler tarafından formüle edilmişti. Massachusetts Clay Matematik Enstitüsü, konunun matematikçi olmayan insanlar tarafından da anlaşılabilmesi için, 400 öğrencinin 100 odada nasıl barındırılabileceğinin hesaplanması örneğini veriyor. Durumu karmaşıklaştırmak için dekan size bir de uyumsuz öğrenci çiftleri listesi vermiş olsun. Ve sizden finalde aldığınız kararda, bu çiftlerin yan yana düşmemesini istesin. Bu, bilgisayar mühendislerinin bir NP problemi dedikleri şeye bir örnektir. 400 başvuru içinden 100 öğrenci seçmenin yollarının toplam sayısı, evrendeki bilinen atom sayısından bile fazladır.
matematikte p problemi vardır.
çözümlerinin bulunması ve doğrulanması kolay olan sorunları ifade eden P'nin, çözümleri neredeyse imkânsız fakat doğrulanmaları kolay olan NP ile aynı olmadığını ispatlanması.
kaynak:ntvmsnbc
