bilgisayar bilimleri alanındaki en meşhur çözülememiş problem.
meşhur abilerimiz kurt gödel ve john von neumann tarafından 1956 yılında ilk kez tanımlanmıştır.

basitçe açıklamak gerekirse:
elimizde bir problem olduğunu düşünün. bu problemin çözümünü bir kahin size söylesin. sizin "acaba söylediği çözüm doğru mu?" sorusunu sorup verdiği cevabı kontrol etmeniz çok kısa^:polinom zaman^ zaman alır.

ancak kahin size cevabı vermek yerine "çöz lan problemi" deseydi, aşırı uzun^:üssel zaman^ bir vakit harcayacaktınız.

p vs. np problem şunu sorar: acaba gerçekten böyle bir şey olabilir mi, yoksa biz bilim insanlarının henüz keşfedemediği bir şeyler mi var?

daha teorik tanımı ise: n input verilen bir turing machine, final state'e ulaşan her yolu garantlemek için n'in üssel bir fonksiyonuna ihtiyaç duyuyorsa, bu problem np bir problemdir. acaba bu state'leri bir şekilde n cinsinden polinom sayıda state'e indirmek mümkün müdür?