P完全問題（P-complete problem）是2018年全國科學技術名詞審定委員會公布的計算機科學技術名詞。
基本介紹
- 中文名：P完全問題
- 外文名：P-complete problem
- 所屬學科：計算機科學技術
- 公布時間：2018年
定義,出處,
定義
如果一個問題A是多項式時間可計算的，而且任何一個多項式時間可計算的問題均可在對數空間多一歸約到A，則稱A是一個P完全問題。
出處
《計算機科學技術名詞 》第三版
P完全問題
相關詞條
- P完全問題
P完全問題（P-complete problem）是2018年全國科學技術名詞審定委員會公布的計算機科學技術名詞。定義如果一個問題A是多項式時間可計算的，而且任何一個多項式時間可計算的問題均可在對數空間多一歸約到A，則稱...
- NP完全問題
NP完全問題(NP-C問題)，是世界七大數學難題之一。 NP的英文全稱是Non-deterministic Polynomial的問題，即多項式複雜程度的非確定性問題。簡單的寫法是 NP=P？，問題就在這個問號上，到底是NP等於P，還是NP不等於P。詳細信息 P類問題 ：所有可以在多項式時間內求解的判定問題構成P類問題。判定問題 ：判斷是否有一...
- NP-Complete(計算複雜性中的NP完全)
NP完全或NP完備（NP-Complete，縮寫為 NP-C 或 NPC），是計算複雜度理論中，決定性問題的等級之一。NPC 問題，是NP（非決定性多項式時間）中最難的決定性問題。因此NP完備問題應該是最不可能被化簡為P（多項式時間可決定）的決定性問題的集合。釋義 一個決定性問題C若是為NPC，則代表它對NP是完備的，這表示：...
- NP完全性
NP完全問題就是NP中最難問題的一種形式化。多項式時間歸約假定給了兩個問題類q和q0，如果存在一個確定型圖靈機Mq和一個多項式P，對於q中任意一個實例x，Mq都能在P(n)時間內計算出q0中一個實例y(其中n是實例x的編碼長度)，使得x是q中有肯定回答的實例，若且唯若y是q0中有肯定回答的實例，我們就說q...
- P類問題
所謂P類和NP類，都是指問題的集合。由於確定的圖靈機可以看作不確定的圖靈機的一種特殊情形，因此這兩類問題的集合之間存在子集關係，即P屬於NP。NP完全問題 NP-完全問題( Np-complete problem)是計算複雜性理論中最重要的一部分內容。在計算科學和計算機科學理論中，NP完全問題也有著十分重要的地位。因為其重要性...
- 最大團問題
問題描述 給定無向圖G=(V,E)，其中V是非空集合，稱為頂點集；E是V中元素構成的無序二元組的集合，稱為邊集，無向圖中的邊均是頂點的無序對，無序對常用圓括弧“( )”表示。如果 ，且對任意兩個頂點u，v∈U有(u,v)∈E，則稱U是G的完全子圖。G的完全子圖U是G的團。G的最大團是指G的最大完全...
- 完全數問題
完全數問題(perfect number problem)若正整數n的所有正因數之和等於2n，則稱n為完全數.可表達為a(n)=2n，式中a(n)是n的所有正因數之和.人們問道:完全數是否有無窮多? 早在古希臘人們就知道了兩個完全數:6,28.數學家歐幾里得(Euclid )的《幾何原本》中曾給出過完全數的定義，並證明了完全數的一個重要...
- 布爾可滿足性問題
人們普遍認為PSPACE完全問題比NP中的任何問題都嚴格，儘管尚未得到證實。使用高度並行的P系統，可以線上性時間內解決QBF-SAT問題。普通的SAT詢問是否存在至少一個使公式成立的變數賦值。各種變體處理此類任務的數量：MAJ-SAT詢問所有作業的大部分是否使公式為TRUE。眾所周知，PP是一種機率類。#SAT，計算有多少變數賦值...
- 蓋梯爾問題
蓋梯爾問題也稱做“蓋梯爾悖論”，“蓋梯爾例證”。自從柏拉圖的《泰阿泰德篇》以來，命題知識一直被標準地定義為已被證明的真信念，這種分析如下：A知道P，若且唯若（1）P是真的，（2）A相信P，（3）A有充分的理由相信P。這種傳統的三重分析受到了蓋梯爾在題為《明辨了的信念就是知識嗎？》（《分析》，...
- 哥德爾不完全性定理(數理邏輯術語)
於是，為了確立系統S的相容性，就要構建另一個系統T，但是T中的證明並不是完全可信的，除非不使用S就能確立T的相容性。舉個例子，自然數上的皮亞諾公理的相容性可以在集合論中證明，但不能單獨在自然數理論範圍內證明。這對大衛·希爾伯特的著名的未解決的23個數學問題中的第二個給出了一個否定回答。理論上，...
- NEXPTIME
如果有個問題，使用一般的圖表示法，像是連線矩陣，去解決時是個NP-完全問題，那么使用簡潔電路的表示來解決這個問題是NEXPTIME-完全，因為輸入的大小跟前者相比是成指數速率縮小。舉個簡單的例子，使用簡潔電路的表示法找一張圖的哈密頓圖是NEXPTIME-完全。如果P= NP，那么NEXPTIME = EXPTIME；更精確的說，E ≠ ...
- 非確定性多項式難題
NPC(NP Complete，NP完全)問題 計算機科學家將NP問題中最困難的稱為NPC問題。NPC問題有一個令人驚訝的性質，即如果一個NPC問題存在多項式時間算法，那么所有NP問題都可以在多項式時間內求解，即P=NP成立。這是因為每一個NPC問題都可以在多項式時間內轉化成任何一個NP問題。只要任意一個NPC問題找到了一個多項式算法...
- NP(未解難題)
NP完全 要解決P = NP問題，NP完全的概念非常有用。不嚴格的講，NP完全問題是NP類中“最難”的問題，也就是說它們是最可能不屬於P類的。這是因為任何NP中的問題可以在多項式時間內變換成為任何特定NP完全問題的一個特例。例如，旅行商問題的判定問題版本是NP完全的。所以NP中的任何問題的任何特例可以在多項式時...
- 機率論(數學分支)
機率論是研究隨機現象數量規律的數學分支，是一門研究事情發生的可能性的學問。但是最初機率論的起源與賭博問題有關。16世紀，義大利的學者吉羅拉莫·卡爾達諾（Girolamo Cardano）開始研究擲骰子等賭博中的一些簡單問題。機率與統計的一些概念和簡單的方法，早期主要用於賭博和人口統計模型。隨著人類的社會實踐，人們需要...
- 貝葉斯公式
例如：一座別墅在過去的 20 年裡一共發生過 2 次被盜，別墅的主人有一條狗，狗平均每周晚上叫 3 次，在盜賊入侵時狗叫的機率被估計為 0.9，問題是：在狗叫的時候發生入侵的機率是多少？我們假設 A 事件為狗在晚上叫，B 為盜賊入侵，則以天為單位統計，P(A) = 3/7，P(B) = 2/(20*365) = 2/7300...
- P值
選擇一個檢驗統計量(例如z 或Z 統計量) ，該統計量的分布在假定的參數取值為真時應該是完全已知的；從研究總體中抽取一個隨機樣本計算檢驗統計量的值計算機率P值（或者觀測）的顯著水平，即在假設為真時的前提下，檢驗統計量大於或等於實際觀測值的機率；若P 可是，那個年代，由於硬體的問題，計算P值並非易事，...
- 歐拉定理
除簡單多面體外，還有非簡單多面體。例如，將長方體挖去一個洞，連結底面相應頂點得到的多面體。它的表面不能經過連續變形變為一個球面，而能變為一個環面。其歐拉示性數f (p)=16+16-32=0，即帶一個洞的多面體的歐拉示性數為0。5．利用歐拉定理可解決一些實際問題 如：為什麼正多面體只有5種，足球與C60的...
- 性高潮
在中國，學生的在校性行為及其法律問題需要引起更多關注。性高潮的產生是生殖器官的反射行為，由脊髓控制，不一定由意識控制。在性侵害行為中，許多受害者在非自願情況下產生的性高潮稱為非自願性高潮。非自願性行為產生的性高潮常常使受害者感到羞恥，產生自責歸因，影響其身心健康發展。然而性高潮本身並沒有錯，受害者...
- 皮亞諾公理
定義a/b為a(1/b)，如果b非零。可以驗證，這樣的定義與通常理解的有理數加減乘除法是一致的。如果大家對這方面問題感興趣的話，可以嘗試證明前文中“可以驗證”的內容，也可以看看來知道具體是怎么證明的。實數、微積分 皮亞諾公理是義大利數學家皮亞諾在1889 年發表的。雖然描述這套公理體系的數學語言發生過不...
- 關於隨機MAX SAT和(2+p)-SAT模型可滿足閾值的研究
《關於隨機MAX SAT和(2+p)-SAT模型可滿足閾值的研究》是依託北京工商大學，由周廣艷擔任項目負責人的數學天元基金項目。項目摘要 SAT問題作為最經典的約束滿足問題，其相變現象及閾值附近複雜性的研究是揭示NP完全問題難解本質的關鍵之一。本項目將圍繞隨機MAX SAT和隨機(2+p)-SAT兩大問題進行研究，旨在通過使用嚴...
- 弗拉蒂尼引理
此類型最小的群GL(2,3)的討論，見Visualizing GL(2,p)。有限群和對稱有直接地關接，當其被限制在有限個轉變時。 其證明為，連續對稱，如李群中的，也會導致有限群，如外爾群。在此一方面，有限群和其性質將能夠用在如理論物理問題的重要地方，即使其用途在一開始並不顯著。每一素數階的有限群都是循環群。
- 形式邏輯(邏輯學術語)
涉及思維內容方面的問題不是形式邏輯所研究的對象，而是其他具體科學所研究的對象。形式邏輯只研究思維形式而不研究思維內容，這不是要把思維形式和思維內容割離開來。相反的，形式邏輯研究思維形式，正是為了使人們自覺地掌握思維形式的規律，從而更好地把思維形式和思維內容結合起來以正確反映客觀現實。把思維形式和思維...
- 三段論推理
三段論推理：思維時，大腦首先用一個人為定義的內容極為明確的、囊括的範圍比較大的總的原則A（簡稱“大前提”），再通過科學實驗尋找另外一個概念小前提B，B的概念的全部內涵能夠一定被包含在大前提A內、並且用文字描述的B的概念的內容時，不能人為與大前提A的內容本質完全一樣（B簡稱小前提），然後按照小前提B...
- 排列組合(組合數學中的一種)
中國郵差問題：由中國組合數學家管梅谷教授提出。郵遞員要穿過城市的每一條路至少一次，怎樣行走走過的路程最短？這不是一個NP完全問題，存在多項式複雜度算法：先求出度為奇數的點，用匹配算法算出這些點間的連線方式，然後再用歐拉路徑算法求解。這也是圖論的問題。任務分配問題（也稱婚配問題）：有一些員工要完成...
- 機率(統計學術語)
問題主要是兩個：擲骰子問題和比賽獎金分配問題。機率是度量偶然事件發生可能性的數值。假如經過多次重複試驗(用X代表)，偶然事件(用A代表)出現了若干次(用Y代表)。以X作分母，Y作分子，形成了數值(用P代表)。在多次試驗中，P相對穩定在某一數值上，P就稱為A出現的機率。如偶然事件的機率是通過長期觀察或大量...
- 方差分析(數學術語)
例如，分析不同施肥量是否給農作物產量帶來顯著影響，考察地區差異是否影響婦女的生育率，研究學歷對工資收入的影響等。這些問題都可以通過單因素方差分析得到答案。單因素方差分析的第一步是明確觀測變數和控制變數。例如，上述問題中的觀測變數分別是農作物產量、婦女生育率、工資收入；控制變數分別為施肥量、地區、學歷...
- 總供給曲線
因此，在運用總需求—總供給模型分析問題時，總供給曲線的斜率大小是很重要的。總供給曲線的斜率反映了總供給量對價格變動的反應程度。總供給曲線的斜率大（即總供給曲線較為陡峭），說明總供給量對價格變動的反應小。總供給曲線的斜率小（即總供給曲線較為平坦），說明總供給量對價格變動的反應大。總供給曲線的斜率...
- 泊松過程
一種累計隨機事件發生次數的最基本的獨立增量過程。例如隨著時間增長累計某電話交換台收到的呼喚次數，就構成一個泊松過程。泊松過程是由法國著名數學家泊松（Poisson, Simeon-Denis）（1781—1840）證明的。 1943年C.帕爾姆在電話業務問題的研究中運用了這一過程，後來Α.Я.辛欽於50年代在服務系統的研究中又進一步...
