P, çokterimli zamanda (belirlenimli Turing Makinesi ile) çözülebilen karar problemlerini içeren karmaşıklık sınıfıdır. P sınıfı pek çok doğal problemi içerse de bazı önemli problemlerin (bk. NP) P içerisine girip girmediği bilinmemektedir.
P harfi "polynomial", NP harfleri ise "non-deterministic polynomial" ifadelerini temsil eder, Türkçe karşılıkları "polinom" ve "belirleyici olmayan polinom"dur. "P eşittir NP?" ise hesaplama teorisi'nin en temel ve meşhur problemidir.
Nen karar problemlerini içeren karmaşıklık sınıfıdır.
Seyyar satıcı problemi yöneylem araştırması ve teorik bilgisayar bilimi alanlarında incelenen bir "kombinatorik optimizasyon" problemidir.
Üstel zamanda çalışan bir algoritma, bir Turing makinesinin girişin uzunluğunun en fazla 
Sırt çantası problemi bir klasik yöneylem araştırması ve matematiksel olarak "kombinatorik optimizasyon" problemidir. Çözüm algoritması bakımından sırt çantası problemi en ünlü NP-hard problemleri arasındadır.
Olasılık kuramı ve istatistik bilim kollarında, binom dağılımı n sayıda iki kategori (yani başarı/başarısızlık, evet / hayır, 1/0 vb) sonucu veren denemelere uygulanır. Araştırıcının ilgi gösterdiği kategori başarı olarak adlandırılır. Bu türlü her bir deneyde, bağımsız olarak, başarı (=evet=1) olasılığının p olduğu (ve yalnızca iki kategori sonuç mümkün olduğu için başarısızlık olasılığının 1 - p olduğu) bilinir. Bu türlü bağımsız n sayıda denemeler serisi içinde elde edilen başarı sayısının ayrık olasılık dağılımı binom dağılım olarak tanımlanır. Bir binom dağılım sadece iki parametre ile, yani n ve p ile tam olarak tanımlanır. Matematik notasyon olarak bir rassal değişken X binom dağılım gösterirse şöyle ifade edilir:
Olasılık kuramında ve istatistikte, hipergeometrik dağılım sonlu bir ana kütle içinden tekrar geri koymadan birbiri arkasına n tane nesnenin çekilmesi işlemi için başarı sayısının dağılımını bir ayrık olasılık dağılımı şekilde betimler.
SAT problemi bir NP-tam sınıfı problemidir.
Hamilton Yolu, yönlü veya yönsüz bir grafta Hamilton yolu veya Hamilton devresinin olup olmadığının kararının verilmesinin problemidir.
3SAT ve KLIK problemleri, Turing makinasından polinom zamanda kararlaştırılabilen NP problemleri arasında yer alır. Bu problemlerin birbirinin cinsine çevrilmesine indirgeme denilir.
Köşe Örtme, bir çizge (graf) içerisindeki tüm kenarların en az sayıda seçilebilecek düğüm ile kapsanabilir olup olmadığının bulunması problemidir. Bu problemin NP sınıfı içerisinde olduğu bilinmektedir. Amaç, bu problemin NP-Tam sınıfında olup olmadığının ispatıdır.
Bilgisayar bilimlerinde, alt küme toplamı problemi karmaşıklık kuramında ve kriptografide önemli yeri olan bir problemdir.
Hesaplamalı fizik, fizik sorunlarını çözebilmek için sayısal algoritmaların üretilmesi ve gerçeklenmesini içerir. Genelde kuramsal fizikin bir alt dalı olarak değerlendirilir ancak bazen de kuramsal ve deneysel fizik arasında orta bir dal olarak da düşünülür.
Bilgisayar bilimi felsefesi, bilgisayar bilimi çalışmasında ortaya çıkan felsefi sorularla ilgilidir. Fizik felsefesi veya matematik felsefesi gibi bir bilgisayar bilimi felsefesi geliştirmeye yönelik bazı girişimlere rağmen, bilgisayar bilimi felsefesinin içeriği, amacı, odağı veya konusu hakkında hala ortak bir anlayış yoktur. Bilgisayar programlarının soyut doğası ve bilgisayar biliminin teknolojik tutkuları nedeniyle, bilgisayar bilimi felsefesinin kavramsal sorularının çoğu, bilim felsefesi, matematik felsefesi ve teknoloji felsefesi ile de karşılaştırılabilir.
Sayı teorisinde, asal çarpanlara ayırma bir bileşik sayının, çarpıldıklarında yine aynı sayıyı verecek şekilde, bir ve kendisi dışındaki bölenlerine ayrılmasıdır.
Milenyum (Binyıl) Problemleri, 2000 yılında Clay Matematik Enstitüsü tarafından belirlenmiş matematiğin farklı dallarındaki yedi probleme verilen addır. Ocak 2024 itibarı ile problemlerden altısı henüz çözülmemiştir.
Hesaplamalı karmaşıklık teorisi, hesaplama problemlerini kendi zorluklarına göre sınıflandırmaya ve bu sınıfları birbirleriyle ilişkilendirmeye odaklanan teorik bilgisayar bilimlerinde hesaplama teorisinin bir dalıdır. Bir hesaplama probleminde prensip, algoritmada belirtilen matematiksel adımların mekaniğe uygulanması yoluyla probleme yaklaşmaktır. Ve bununla beraber hesaplama karmaşıklık teorisindeki problemler, eşdeğer bir bilgisayar tarafından çözülebilen ortamlarda kullanılır.
Hesaplamalı karmaşıklık kuramında NP-tam hem NP hem NP-zor olan problemlerin sınıfıdır. Dolayısıyla bu sınıftaki problemler NP sınıfının en zor problemleridir. Bu problemleri polinomsal zamanda çözebilen algoritma bulunmamaktadır.
Tekli sayı sistemi, doğal sayıları temsil eden en basit sayı sistemidir: bir N sayısını temsil etmek için, 1'i temsil eden bir simge N kez tekrarlanır.