NP完全和脱氧核糖核酸

快捷方式: 差异，相似，杰卡德相似系数，参考。

NP完全和脱氧核糖核酸之间的区别

NP完全 vs. 脱氧核糖核酸

NP完全或NP完備（NP-Complete，縮寫為NP-C或NPC），是計算複雜度理論中，決定性問題的等級之一。NPC問題，是NP（非決定性多項式時間）中最難的決定性問題。因此NP完備問題應該是最不可能被化簡為P（多項式時間可決定）的決定性問題的集合。若任何NPC問題得到多項式時間的解法，那此解法就可應用在所有NP問題上。更詳細的定義容下敘述。 一個NPC問題的例子是子集合加總問題，題目為 這個問題的答案非常容易驗證，但目前沒有任何一個夠快的方法可以在合理的時間內（意即多項式時間）找到答案。只能一個個將它的子集取出來一一測試，它的時間複雜度是Ο(2n)，n是此集合的元素數量。. --氧核醣核酸（deoxyribonucleic acid，縮寫：DNA）又稱--氧核醣核酸，是一種生物大分子，可組成遺傳指令，引導生物發育與生命機能運作。主要功能是資訊儲存，可比喻為「藍圖」或「配方」。其中包含的指令，是建構細胞內其他的化合物，如蛋白質與核醣核酸所需。帶有蛋白質編碼的DNA片段稱為基因。其他的DNA序列，有些直接以本身構造發揮作用，有些則參與調控遺傳訊息的表現。 DNA是一種長鏈聚合物，組成單位稱為核苷酸，而糖類與磷酸藉由酯鍵相連，組成其長鏈骨架。每個糖單位都與四種鹼基裡的其中一種相接，這些鹼基沿著DNA長鏈所排列而成的序列，可組成遺傳密碼，是蛋白質氨基酸序列合成的依據。讀取密碼的過程稱為轉錄，是根據DNA序列複製出一段稱為RNA的核酸分子。多數RNA帶有合成蛋白質的訊息，另有一些本身就擁有特殊功能，例如核糖體RNA、小核RNA與小干擾RNA。 在細胞內，DNA能組織成染色體結構，整組染色體則統稱為基因組。染色體在細胞分裂之前會先行複製，此過程稱為DNA複製。對真核生物，如動物、植物及真菌而言，染色體是存放於細胞核內；對於原核生物而言，如細菌，則是存放在細胞質中的拟核裡。染色體上的染色質蛋白，如組織蛋白，能夠將DNA組織並壓縮，以幫助DNA與其他蛋白質進行交互作用，進而調節基因的轉錄。.

布尔可满足性问题

可滿足性（英語：Satisfiability）是用來解決給定的真值方程式，是否存在一组变量赋值，使問題为可满足。布爾可滿足性問題（Boolean satisfiability problem；SAT)）屬於決定性問題，也是第一个被证明屬於NP完全的问题。此問題在電腦科學上許多領域的皆相當重要，包括電腦科學基礎理論、演算法、人工智慧、硬體設計等等。.

NP完全和布尔可满足性问题 · 布尔可满足性问题和脱氧核糖核酸 · 查看更多 »

哈密頓路徑問題

哈密頓路徑問題（Hamiltonian path problem）與哈密頓迴圈問題（Hamiltonian cycle problem）屬於數學中的圖論。此問題是用來決定一個圖上的哈密頓路徑或哈密頓迴圈。兩個問題皆為NP完全。為旅行推銷員問題的特殊案例。.

NP完全和哈密頓路徑問題 · 哈密頓路徑問題和脱氧核糖核酸 · 查看更多 »

图灵机

图灵机（），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。.

NP完全和图灵机 · 图灵机和脱氧核糖核酸 · 查看更多 »