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.
Büyük O (Big-Oh) gösterimi matematiksel bir gösterim olup işlevlerin (fonksiyonların) asimptotik davranışlarını tarif etmek için kullanılır. Bir işlevin büyümesinin asimptotik üst sınırını daha basit başka bir işlev cinsinden tanımlanması demektir. İki temel uygulama alanı vardır: matematik alanında genellikle kırpılmış bir sonsuz serinin kalan terimini karakterize etmek için kullanılır; bilgisayar bilimlerinde ise algoritmaların bilgi işlemsel karmaşıklığının çözümlemesi için kullanılır.
Lineer zamanda çalışan bir algoritma, bir Turing makinesinin girişin uzunluğunun en fazla n katı tane adımda çözebildiği bir problemdir. Lineer zaman, polinomsal zamanın bir alt kümesidir.
P, çokterimli zamanda çö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 P içerisine girip girmediği bilinmemektedir.
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 
katı tane adımda çözebildiği bir problemdir. Doğal olarak, üstel zaman polinomsal zamanı içine alabilir.
Kolmogorov karmaşıklığı, bilgisayar biliminde, bir metin parçası gibi bir nesneyi tanımlamak için kullanılması gereken bilgi işlemsel kaynakların ölçüsü.
Matematik biliminde, özellikle yöneylem araştırması uygulamalı dalında, doğrusal programlama problemleri bir doğrusal amaç fonksiyonunun doğrusal eşitlik ve/veya eşitsizlik kısıtlamalarını sağlayacak şekilde optimizasyon yapılmasıdır. Bir optimizasyon modeli eğer sürekli değişkenlere ve tek bir doğrusal amaç fonksiyonuna sahipse ve tüm kısıtlamaları doğrusal eşitlik veya eşitsizliklerden oluşuyorsa, doğrusal (lineer) program olarak adlandırılır. Başka bir deyişle, modelin tek-amaçlı fonksiyonu ve tüm kısıtlamaları, süreklilik gösteren karar değişkenlerinin ağırlıklı toplamlarından oluşmalıdır.
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.
Savitch Teoremi, uzay karmaşıklığını konu edinen ve bu hususta sonuca varan en eski teoremlerden biridir. Belirlenimsiz makinelerin belirlenimli makinelere dönüştürülmesinde, gerekli olan uzay karmaşıklığını incelemiştir ve beklenenden çok daha küçük uzay gereksinimi olduğunu ortaya koymuştur. Daha formal bir ifadeyle, 
uzay kullanan bir belirlenimsiz Turing makinesi, belirlenimli bir turing makinesine dönüştürülürken 
uzay gerektirir.
Bilgisayar bilimlerinde, alt küme toplamı problemi karmaşıklık kuramında ve kriptografide önemli yeri olan bir problemdir.
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.
18. yy. ve sonrasında geliştirilmiş, genellikle vektörel mekanik olarak nitelendirilen ve orijinalinde Newton mekaniği olarak bilinen analitik mekanik, klasik mekaniğin matematiksel fizik kaynaklarıdır. Model harekete göre analitik mekanik, Newton’un vektörel enerjisinin yerine, hareketin iki skaler özelliği olan kinetik enerjiyi ve potansiyel enerjiyi kullanır. Bir vektör, yön ve nicelik ile temsil edilirken bir skaler, nicelik ile(yoğunluğu belirtirken) temsil edilir. Özellikle Lagrange mekaniği ve Hamilton mekaniği gibi analitik mekanik de, sorunları çözmek için bir sistemin kısıtlamalarının ve tamamlayıcı yollarının kavramını kullanarak klasik mekaniğin kullanım alanını etkili bir şekilde yapılandırır. Schrödinger, Dirac, Heisenberg ve Feynman gibi kuram fizikçileri bu kavramları kullanarak kuantum fiziğini ve onun alt başlığı olan kuantum alan teorisini geliştirdiler. Uygulamalar ve eklemelerle, Einstein’a ait kaos teorisine ve izafiyet teorisine ulaşmışlardır. Analitik mekaniğin çok bilindik bir sonucu, modern teorik fiziğin çoğunu kaplayan Noether teoremidir.
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.
