NP-complete問題列表
非決定性多項式集合完備問題列表（NP完備問題列表）列出了一些較常見的NP完備問題。此類問題數以千計，因此本列表只列出一些較常見的和大眾文化中較為知名的。 的著作收錄了許多這類問題。 圖與超圖 圖經常出現在日常應用中。例如生物網絡或社交網絡，在某些情況下包含數百、數千甚至數十億個節點（例如Facebook或LinkedIn）。 三維匹配問題 ::NP完全的特例包括最小極大匹配問題， 秩著色（Rank coloring） k-中國郵遞員問題…
标签：#數學列表
共 7 篇文章
複雜度類列表
許多複雜度類都有一個前面加上'Co'的同伴，這是包含原來複雜度類裡面所有問題的補集的一個複雜度類。像是，若一個語言屬於NP，則此語言的補集則屬於Co-NP。（注意這裡不代表NP的補集就等同於Co-NP - 有一些語言同時是NP也是Co-NP，也有語言兩者皆非。） 一個複雜度類裡面"最難的問題"代表這個複雜度類裡面所有的問題都可以歸約為這個問題。此外，歸約過程本身是這個複雜度或者比他更簡單的問題類別裡面。 如果找不到想要看的複雜度類（例如…
概形論術語
這是概形論術語。欲知代數幾何中概形的簡介，請見條目仿射概形、射影空間、層及概形。本條目旨在列出概形論中的基本技術定義與性質。 點 一個概形 S 是一個局部賦環空間，故也是拓撲空間，但「S 的點」具有三重涵義： 拓撲空間意義下的點。 T-值點：對任一概形 T，一個 T-值點是指一個態射 T \to S。 幾何點：當 S 定義在一個域 K 上時（換言之 S 是 \mathrm{Spec}(K)-概形），一個幾何點乃是一個 \mathrm{S…
积分表
由于列表比较长，积分表被分为以下几个部分： 有理函数积分表 无理函数积分表 指数函数积分表 对数函数积分表 高斯函数积分表 三角函数积分表 反三角函数积分表 双曲函数积分表 * 反双曲函数积分表 含有ax+b的积分 :\int\ (ax+b)^n\mbox{d}x=\frac{(ax+b)^{n+1}}{a(n+1)}+C,n\neq -1 :\int\frac{1}{ax+b}\mbox{d}x=\frac{1}{a}\ln \lef…
級數列表
本表 列出基本或常見的有限級數與無限級數的計算公式。 規定0^0=1； B_n(x)表示Bernoulli多項式； B_n表示Bernoulli數，其中，B_1=-\frac{1}{2}； E_n表示Euler數； \zeta(s)表示黎曼ζ函數； \Gamma(z)表示Γ函數； \psi_n(z)表示多伽瑪函數； \operatorname{Li}_s(z)表示多重對數函數。 冪求和 :參見等冪求和。 \sum_{k=0}^m k^{…
卡普的二十一個NP-完全問題
在計算複雜度理論內，一個極度重要的成就是史提芬·古克在1971年證明出了第一個NP-完全問題— 布爾可滿足性問題。在1972年，理查德·卡普將這個想法往前推進，發表了他著名的論文"Reducibility Among Combinatorial Problems"，其內證明了21個不同的，均因為其難解而惡名昭彰的組合數學與圖論問題，是NP-完全問題。 藉由展示出許多研究上面重要的問題是NP-完全問題，卡普促進了研究NP，NP-完備性，以…
小群列表
下面的數學列表包含著以群同構來分之小階有限群。 這個列表可以被用來決定一個給定的有限群G會同構於哪一種群：首先確定G的階，然後再找下面列表中有相同階的候選群。若知道G為可換與否，某些的候選群便可以立刻被刪掉。為了分別剩下的候選群，可以看給定之群內每個元素的階，並對照候選群內每個元素的階。 術語 Zn：其階為n之循環群(通常C*n或Z/nZ之符號也會被使用)。 Dihn：其階為2n的二面體群(通常D*n之符號也會被使用，有時則會用D2n)…