Genel bakış
P ile NP problemi, çözümü hızlı biçimde doğrulanabilen her problemin hızlı biçimde çözülebilip çözülemeyeceğini soran hesaplama kuramı problemidir. P sınıfı polinom zamanda çözülebilen, NP ise aday çözümü polinom zamanda doğrulanabilen karar problemlerini içerir. [1]
TEMEL ÖZELLİKLER
P’nin NP’ye eşit olduğu gösterilirse çok sayıda arama ve eniyileme problemi için verimli genel yöntemlerin bulunması mümkün olabilir. Eşit olmadıkları kanıtlanırsa hızlı doğrulamanın her zaman hızlı çözüm anlamına gelmediği kesinleşir. Cook–Levin teoremiyle tanımlanan NP-tam problemler, bu ayrımın merkezindedir; soru Clay Matematik Enstitüsünün Milenyum Problemlerinden biridir. [1]