1. 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* zaman alır.

    ancak kahin size cevabı vermek yerine "çöz lan problemi" deseydi, aşırı uzun* 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?