數理化 : 技術 > np
目錄
No. 1
  np是network processor的縮寫,意為網絡處理器。根據“國際網絡處理器會議”的定義:網絡處理器是一種可編程器件,它特定地應用於通信領域的各種任務,比如包處理、協議分析、路由查找、防火墻、qos等。
  網絡處理器器件內部通常由若幹個微碼處理器和若幹硬件協處理器組成,且多個微碼處理器在np內部並行處理,通過預先編製的微碼來控製處理流程。對於某些復雜的標準操作,如內存操作、路由表查找算法、qos的擁塞控製算法、流量調度算法等,則采用硬件協處理器來進一步提高處理性能,從而實現了業務靈活性和高性能的有機結合。
  np的多種産品形態
  目前np主要用於網絡骨幹設備和網絡接入設備,用來開發從網絡第2層到第7層的各種服務和應用。目前,采用np處理分組交換的廠傢,既有第一梯隊的網絡公司,如思科、北電和朗訊等,也有不少後起之秀,如華為、中興、港灣等。但是,其np用途卻不盡相同:思科寬帶彙聚係列産品使用了思科的並行快速轉發(pxf)np,它被業內稱為“np的鼻祖”;華為在“第五代路由器”ne80/40/20係列産品中全面采用了np;港灣的高端路由器、核心交換機,如nethammer g係列采用了np相關技術;ut斯達康公司選擇了motorola的np作為幾項3g無綫接入網産品的封包轉發引擎……
  哪種np技術更適合防火墻
  我們不難瞭解,由於各廠商所專註的np技術領域不同,决定了np産品之間的差異。目前,國內多數安全廠商在np技術上大都選擇了ibm或intel的np技術。其實,具體選用哪種np技術開發防火墻,因素有很多,包括所選np技術的性能和成熟度、提供np技術的廠商實力和重視程度,以及np技術廠商可提供的支持力度及價格。
  ibm研發的power np係列芯片不僅支持多綫程,且每個綫程都有充足的指令空間,在一個綫程裏完成防火墻功能綽綽有餘。其係列産品中,以np4gs3為代表,該芯片最高端口速率可達oc-48,並具有4.5mbps的報文處理能力和最大4g的端口容量,並且,其擁有ibm創新的帶寬分配技術(bat),是進行下一代係統設計的強大部件。而且,ibm還為開發者提供了軟件架構的解决方案和仿真平臺,大大縮短了開發難度和周期。目前,已經有不少廠傢采用ibm的芯片開發高端防火墻産品,如聯想網禦於2003年10月推出了國內第一款基於np技術的千兆綫速防火墻;2005年,在解决了多項基於多np協同工作的技術難題的基礎上,聯想網禦成功推出了萬兆級的超性能防火墻。
  intel推出的ixp2000係列芯片支持微碼開發,在性能上有了長足的提高,如ixp2400理論上最多可支持2.5gbps的應用,ixp2800則支持10gbps以上的應用。其sdk開發包一般功能十分齊全,模塊化很好,便於開發人員控製。不足的是,ixp2400每個微引擎僅能存儲4k*32位的指令,比較適合開發路由器和交換機這類産品;ixp2800每個微引擎能存儲8k*32位的指令,基本可以滿足防火墻功能開發的需要,但是,由於其性能提高帶來了産品設計與應用復雜度的成倍提高,造成價格十分昂貴。此外,該係列産品的硬件查表功能比較弱,這對於防火墻這類需要大量查表操作的設備來講,是致命的弱點。
  np防火墻將大步前行
  隨着新一代網絡的繼續發展,np將更加倚重綫速、智能化的包處理技術,而不僅僅是簡單的基本性能,np技術的發展將直接影響到np防火墻的發展。據業內專傢調查分析,np技術將嚮着更高的性能、更多功能支持、多種技術並存和標準化等特徵發展,基於np的防火墻産品將隨着np的發展大步前行。
  更高的性能
  五年來,網絡的傳輸速度每年翻一番,幾年前的主幹網速度是155mb/s,現在已經到了10gb/s,兩到三年內又會提高到40gb/s,網絡處理器也必須滿足這種變化。np性能的提高,將直接推動防火墻性能的提高。
  更多的功能支持
  隨着網絡處理器在更多領域中的應用,網絡處理器必須具有更多的功能支持,如深度內容處理和ipv6協議識別,以能適應防火墻等安全設備的需求。
  多種技術並存
  np不是萬能的,它並不會完全取代通用處理器和asic在網絡設備中的應用。在對處理性能需求很高的高端設備中,asic仍然具有很強的生命力,可以預見的是,在數據層面、控製層面和管理層,通用處理器、np和asic將各司其職,共同為防火墻應用提供靈活的服務。
  實現標準化
  np技術的開發與應用直接促成了網絡處理器論壇(npf)的誕生。npf的成立,將進一步推動np的發展,實現標準化,解决産品互連互通和軟件可移植性等問題。
  涌現龐大的第三方開發隊伍
  隨着標準化工作的深入,再加上網絡處理器本身具有模塊化結構的特點,將涌現出一支龐大的第三方隊伍,在硬件組件、np操作係統、開發工具、軟件應用等方面努力。
  總之,防火墻技術與np技術開始緊密地聯繫在一起,np技術的變革將推動防火墻技術嚮着更高性能、更多功能以及標準化的方向發展。
  元素符號: np英文名: neptunium中文名: 鎿
  相對原子質量: 237.048常見化合價: +3,+4,+5,+6電負性: 1.36
  外圍電子排布: 5f4 6d1 7s2核外電子排布: 2,8,18,32,23,8,2
  同位素及放射綫: np-235[1.08y] np-236[155000y] np-236m[22.5h] np-237(放 α[2140000y]) np-238[2.11d] np-239[2.35d] np-240[1.03h] np-240m[7.22m]
  熱容:j /(mol· k)
  29.46
  導熱係數:w/(m·k)
  6.3
  導電性:10^6/(cm ·Ω)
  0.00822
  熔化熱:(千焦/摩爾)
  5.190
  電子親合和能: 0 kj·mol-1
  第一電離能: 600 kj·mol-1 第二電離能: 0 kj·mol-1 第三電離能: 0 kj·mol-1
  單質密度: 20.45 g/cm3 單質熔點: 640.0 ℃ 單質沸點: 3902.0 ℃
  原子半徑: 0 埃 離子半徑: 埃 共價半徑: 0 埃
  常見化合物: npo2 npf4
  發現人: 麥剋米倫、阿貝爾森時間: 1940地點: 美國
  名稱由來:
  得名於海王星的名字“neptune”。
  元素描述:
  稀有的銀白色放射性金屬。
  元素來源:
  用慢中子轟擊鈾原子而得到。
  元素用途:
  沒有什麽實際用途。
  p/np問題是在理論信息學中計算復雜度理論領域裏至今沒有解决的問題,它被“剋雷數學研究所”(clay mathematics institute, 簡稱cmi)在千禧年大奬難題中收錄。p/np問題中包含了復雜度類p與np的關係。1971年史提芬·古剋(stephen a. cook) 和 leonid levin 相對獨立的提出了下面的問題,即是否兩個復雜度類p和np是恆等的(p=np?)。
  p和np
  復雜度類p包含所有那些可以由一個確定型圖靈機在多項式表達的時間內解决的問題;類np由所有其肯定解可以在給定正確信息的多項式時間內驗證的决定問題組成,或者等效的說,那些解可以在非確定圖靈機上在多項式時間內找出的問題的集合。很可能,計算理論最大的未解决問題就是關於這兩類的關係的:
  p和np相等嗎?
  在2002年對於100研究者的調查,61人相信答案是否定的,9個相信答案是肯定的,22個不確定,而8個相信該問題可能和現在所接受的公理獨立,所以不可能證明或證否。 對於正確的解答,有一個,000,000美元的奬勵。
  np-完全問題(或者叫npc)的集合在這個討論中有重大作用,它們可以大致的被描述為那些在np中最不像在p中的。(確切定義細節請參看np-完全)理論計算機科學家現在相信p, np,和npc類之間的關係如圖中所示,其中p和npc類不交。
  假設p ≠ np的復雜度類的圖解.如p = np則三個類相同.本質上,p = np問題問道:如果是/不是問題的正面答案可以很快驗證,其答案是否也可以很快計算?這裏有一個給你找點這個問題的感覺的例子。給定一個大數y,我們可以問y是否是復合數。例如,我們可能問53308290611是否有非平凡的因子。回答是肯定的,雖然手工找出一個因子很麻煩。從另一個方面講,如果有人聲稱答案是"對,因為224737可以整除53308290611",則我們可以很快用一個除法來驗證。驗證一個數是除數比首先找出除數來簡單得多。用於驗證一個正面答案所需的信息也稱為證書。所以我們的結論是,給定 正確的證書,問題的正面答案可以很快的(也就是,在多項式時間內)驗證,而這就是這個問題屬於np的原因。雖然這個特定的問題,最近被證明為也在p類中(參看下面的關於"質數在p中"的參考),這一點也不明顯,而且有很多類似的問題相信不屬於類p。
  限製到是/不是問題並沒有改變問題;即使我們允許更復雜的答案,最後的問題(是否fp = fnp)是等價的。
  形式化定義
  更正式一些,一個决定問題是一個取一些字符串為輸入並要求輸出為是或否的問題。若有一個算法(譬如圖靈機,或一個lisp或pascal的程序並有無限的內存)能夠在最多nk步內對一個串長度為n的輸入給出正確答案,其中k是某個不依賴於輸入串的常數,則我們稱該問題可以在多項式時間內解决,並且將它置入類p。直觀的講,我們將p中的問題視為可以較快解决的問題。
  現在假設有一個算法a(w,c)取兩個參數,一個串w,也就是我們的决定問題的輸入串,而另一個串c是“建議證明”,並且使得a在最多nk步之內産生“是/否”答案(其中n是w的長度而k不依賴於w)。進一步假設
  w是一個答案為“是”的例子,當且僅當,存在c使得a(w,c)返回“是”。
  則我們稱這個問題可以在非决定性多項式時間內解决,且將它放入np類。我們把算法a作為一個所建議的證明的檢驗器,它運行足夠快。(註意縮寫np代表“non-deterministic(非確定性)polynomial(多項式)”而不是代表“non-polynomial(非多項式)。)
  np完全
  要解决p = np問題,np完全的概念非常有用。不嚴格的講,np完全問題是np類中“最難”的問題,也就是說它們是最可能不屬於p類的。這是因為任何np中的問題可以在多項式時間內變換成為任何特定np完全問題的一個特例。例如,旅行商問題的判定問題版本是np完全的。所以np中的任何問題的任何特例可以在多項式時間內機械地轉換成旅行商問題的一個特例。所以若旅行商問題被證明為在p內,則p = np!旅行商問題是很多這樣的np完全的問題之一。若任何一個np完全的問題在p內,則可以推出p = np。不幸的是,很多重要的問題被證明為np完全,但沒有一個有已知快速的算法。
  更難的問題
  雖然是否p=np還是未知的,在p之外的問題是已經知道存在的。尋找國際象棋或圍棋最佳走法(在n乘n棋盤上)是指數時間完全的。因為可以證明p ≠ exptime(指數時間),這些問題位於p之外,所以需要比多項式時間更多的時間。判定presburger算術中的命題是否為真的問題更加睏難。fischer和rabin於1974年證明每個决定presburger命題的真偽性的算法有最少2^(2^(cn))的運行時間,c為某個常數。這裏,n是presburger命題的長度。因此,該命題已知需要比指數時間更多的運行時間。不可判定問題是更加睏難的,例如停機問題。它們無法在任何給定時間內解决。
  p真的容易處理嗎?
  上面所有的討論假設了p表示“容易”而“不在p中”表示“睏難”。這是一個在復雜度理論中常見而且有一定準確性的假設,它在實踐中卻不總是真的,原因包括如下幾點:
  它忽略了常數因子。一個需要101000n時間的問題是屬於p的(它是綫性時間的),但是事實上完全無法處理。一個需要10-100002n時間的問題不是在p中的(它是指數時間的),但是對於n 取值直到幾千時還是很容易處理的。
  它忽略了指數的大小。一個時間復雜度n1000屬於p,但是很難對付。已經證明在p中存在需要任意大的指數的問題(參看時間等級定理)。一個時間復雜度2n/1000的問題不屬於p,但對與n直到幾千還是容易應對的。
  它衹考慮了最壞情況的復雜度。可能現實世界中的有些問題在多數時候可以在時間n中解决,但是很偶爾你會看到需要時間2n的特例。這個問題可能有一個多項式的平均時間,但最壞情況是指數式的,所以該問題不屬於p。
  它衹考慮確定性解。可能有一個問題你可以很快解决如果你可以接受出現一點誤差的可能,但是確保正確的答案會難得多。這個問題不會屬於p,雖然事實上它可以很快求解。這實際上是解决屬於np而還不知道是否屬於p的問題的一個辦法(參看rp, bpp)。
  新的諸如量子電腦這樣的計算模型,可能可以快速的解决一些尚未知道是否屬於p的問題;但是,沒有一個它們已知能夠解决的問題是np完全的。不過,必須註意到p和np問題的定義是采用象圖靈機這樣的經典計算模型的屬於表述的。所以,即使一個量子計算機算法被發現能夠有效的解决一個np完全問題,我們衹是有了一個快速解决睏難問題的實際方法,而不是數學類p和np相等的證明。
  計算機科學家為什麽認為p ≠ np
  多數計算機科學家相信p≠np。該信念的一個關鍵原因是經過數十年對這些問題的研究,沒有人能夠發現一個np完全問題的多項式時間算法。而且,人們早在np完全的概念出現前就開始尋求這些算法了(karp的21個np完全問題,在最早發現的一批中,有所有著名的已經存在的問題]])。進一步地,p = np這樣的結果會導出很多驚人的結果,那些結果現在被相信是不成立的,例如np = np和p = ph。
  也有這樣論證的:問題較難求解(np)但容易驗證(p),這和我們日常經驗是相符的。
  從另一方面講,某些研究者認為我們過於相信p ≠ np,而應該也去尋找p = np的證明。例如,2002年中有這樣的聲明:
  傾嚮p≠np的主要論據是在窮盡搜索的領域完全沒有本質進展。也就是說,以我的觀點,一個很弱的論據。算法的空間是很大的,而我們衹是在開始探索的起點。[ . . . ] 費馬最後定理的解决也顯示非常簡單的[sic]問題可能衹有用非常深刻的理論才能解决。
  — moshe vardi,萊斯大學
  過分依賴某種投機不是規劃研究的一個好的導引。我們必須總是嘗試每個問題的兩個方向。偏見可能導致著名的數學家無法解决答案和他們的預計相反的著名問題,雖然他們發展了所有所需的方法。
  — anil nerode, 康奈爾大學
  關於證明的難度的結果
  雖然百萬美元的奬金和大量投入巨大卻沒有實質性結果的研究足以顯示該問題是睏難的,還有一些形式化的結果證明為什麽該問題可能很難解决。
  最常被引用的結果之一設計神喻。假想你有一個魔法機器可以解决單個問題,例如决定一個給定的數字是否為質數,但可以瞬間解决這個問題。我們的新問題是,若我們被允許任意利用這個機器,是否存在我們可以在多項式時間內驗證但無法在多項式時間內解决的問題?結果是,依賴於機器能解决的問題,p = np和p ≠ np二者都可以證明。這個結論的後果是,任何可以修改來證明該機器的存在性的結果不能解决問題。不幸的是,幾乎所有經典的方法和大部分已知的方法可以這樣修改(我們稱它們在相對化)。
  如果這還不算太糟的話,1993年razborov和rudich證明的一個結果表明,給定一個特定的可信的假設,在某種意義下“自然”的證明不能解决p = np問題。 這表明一些現在似乎最有希望的方法不太可能成功。隨着更多這類的定理得到證明,該定理的可能證明有越來越多的陷阱要規避。
  這實際上也是為什麽np完全問題有用的原因:若有一個多項式時間算法,或者沒有一個這樣的算法,對於np完全問題存在,這將用一種相信不被上述結果排除在外的方法來解决p = np問題。
  多項式時間算法
  沒人知道多項式時間算法對於np完全問題是否存在。但是如果這樣的算法存在,我們已經知道其中的一些了!例如,下面的算法正確的接受了一個np完全語言,但是沒人知道通常它需要多久運行。它是一個多項式時間算法當且僅當p = np
  // 接受np完全語言的一個算法子集和。
  //
  // 這是一個多項式時間算法當且僅當p=np
  //
  // “多項式時間”表示它在多項式時間內返回“是”,若
  // 結果是“是”,否則永遠運行。
  //
  // 輸入:s = 一個自然數的有限集
  // 輸出:"是" 如果某個s的子集加起來等於0。
  // 否則,它永遠運行沒有輸出。
  // 註意:"程序數p" 是你將一個整數p寫為二進製,然後
  // 將位串考慮為一個程序。
  // 每個可能的程序都可以這樣産生,
  // 雖然多數什麽也不做因為有語法錯誤。
  //
  for n = 1...infinity
  for p = 1...n
  以s為輸入運行程序數p n步
  if 程序輸出一個不同的整數的列表
  and 所有整數都在s中
  and 整數的和為0
  then
  output "是" 停機
  若p = np,則這是一個接受一個np完全語言的多項式時間算法。“接受”表示它在多項式時間內給出“是”的答案,但允許在答案是“否”的時候永遠運行。
  可能我們想要“解决”子集和問題,而不是僅僅“接受”子集和語言。這表示我們想要它總是停機並返回一個“是”或“否”的答案。是否存在任何可能在多項式時間內解决這個問題的算法?沒有人知道。但是如果這樣的算法存在,那麽我們已經知道其中的一些了!衹要將上面的算法中的if語句替換成下面的語句:
  if 程序輸出一個完整的數學證明
  and 證明的每一步合法
  and 結論是s確實有(或者沒有)一個和為0的子集
  then
  output "是" (或者"不是"如果那被證明了)並停機
  邏輯表述
  p=np問題可以用邏輯命題的特定類的可表達性的術語來重新表述。所有p中的語言可以用一階邏輯加上最小不動點操作(實際上,這允許了遞歸函數的定義)來表達。類似地,np是可以用存在性二階邏輯來表達—也就是,在關係、函數、和子集上排除了全域量詞的二階邏輯。多項式等級,ph中的語言對應與所有的二階邏輯。這樣,“p是np的真子集嗎”這樣的問題可以表述為“是否存在性二階邏輯能夠表達帶最小不動點操作的一階邏輯的所不能表達的語言?”
  花絮
  普林斯頓大學計算機係樓將二進製代碼表述的“p=np?”問題刻進頂樓西面的磚頭上。如果證明了p=np,磚頭可以很方便的換成表示“p=np!”。
  康奈爾大學的hubert chen博士提供了這個玩笑式的p不等於np的證明:“反證法。設p = np。令y為一個p = np的證明。證明y可以用一個合格的計算機科學家在多項式時間內驗證,我們認定這樣的科學家的存在性為真。但是,因為p = np,該證明y可以在多項式時間內由這樣的科學家發現。但是這樣的發現還沒有發生(雖然這樣的科學家試圖發現這樣的一個證明),我們得到矛盾。
  在一些遊戲當中。
  一些玩傢會嚮對方輸入np。no problem意思是沒關係。
  語言學研究常用術語
  np的意思是名詞性成分,應該是nominal(名詞性的)和part(部分)的省稱,名詞性成分包括名詞和名詞性的短語。與之相關的一個詞是vp,意思當然是動詞性成分了,包括動詞和動詞性短語。如有篇語言學論文題目是《確定"s+vp+的(+np)"結構中"的"字歸屬之我見》。如果詞語解釋有誤,希望知者斧正,因為目前網上和詞典還找不到這兩詞的精確解釋,大學問傢又不肯站出來說話,因此我衹能拋磚引玉了。
網絡處理器
  np是Network Processor的縮寫,意為網絡處理器。根據“國際網絡處理器會議”的定義:網絡處理器是一種可編程器件,它特定地應用於通信領域的各種任務,比如包處理、協議分析、路由查找、防火墻、QoS等。
  網絡處理器器件內部通常由若幹個微碼處理器和若幹硬件協處理器組成,且多個微碼處理器在np內部並行處理,通過預先編製的微碼來控製處理流程。對於某些復雜的標準操作,如內存操作、路由表查找算法、QoS的擁塞控製算法、流量調度算法等,則采用硬件協處理器來進一步提高處理性能,從而實現了業務靈活性和高性能的有機結合。
  np的多種産品形態
  目前np主要用於網絡骨幹設備和網絡接入設備,用來開發從網絡第2層到第7層的各種服務和應用。目前,采用np處理分組交換的廠傢,既有第一梯隊的網絡公司,如思科、北電和朗訊等,也有不少後起之秀,如華為、中興、港灣等。但是,其np用途卻不盡相同:思科寬帶彙聚係列産品使用了思科的並行快速轉發(PXF)np,它被業內稱為“np的鼻祖”;華為在“第五代路由器”NE80/40/20係列産品中全面采用了np;港灣的高端路由器、核心交換機,如NetHammer G係列采用了np相關技術;UT斯達康公司選擇了Motorola的np作為幾項3G無綫接入網産品的封包轉發引擎……
  哪種np技術更適合防火墻
  我們不難瞭解,由於各廠商所專註的np技術領域不同,决定了np産品之間的差異。目前,國內多數安全廠商在np技術上大都選擇了IBM或Intel的np技術。其實,具體選用哪種np技術開發防火墻,因素有很多,包括所選np技術的性能和成熟度、提供np技術的廠商實力和重視程度,以及np技術廠商可提供的支持力度及價格。
  IBM研發的Power np係列芯片不僅支持多綫程,且每個綫程都有充足的指令空間,在一個綫程裏完成防火墻功能綽綽有餘。其係列産品中,以np4GS3為代表,該芯片最高端口速率可達OC-48,並具有4.5Mbps的報文處理能力和最大4G的端口容量,並且,其擁有IBM創新的帶寬分配技術(BAT),是進行下一代係統設計的強大部件。而且,IBM還為開發者提供了軟件架構的解决方案和仿真平臺,大大縮短了開發難度和周期。目前,已經有不少廠傢采用IBM的芯片開發高端防火墻産品,如聯想網禦於2003年10月推出了國內第一款基於np技術的千兆綫速防火墻;2005年,在解决了多項基於多np協同工作的技術難題的基礎上,聯想網禦成功推出了萬兆級的超性能防火墻。
  Intel推出的IXP2000係列芯片支持微碼開發,在性能上有了長足的提高,如IXP2400理論上最多可支持2.5Gbps的應用,IXP2800則支持10Gbps以上的應用。其SDK開發包一般功能十分齊全,模塊化很好,便於開發人員控製。不足的是,IXP2400每個微引擎僅能存儲4k*32位的指令,比較適合開發路由器和交換機這類産品;IXP2800每個微引擎能存儲8k*32位的指令,基本可以滿足防火墻功能開發的需要,但是,由於其性能提高帶來了産品設計與應用復雜度的成倍提高,造成價格十分昂貴。此外,該係列産品的硬件查表功能比較弱,這對於防火墻這類需要大量查表操作的設備來講,是致命的弱點。
  np防火墻將大步前行
  隨着新一代網絡的繼續發展,np將更加倚重綫速、智能化的包處理技術,而不僅僅是簡單的基本性能,np技術的發展將直接影響到np防火墻的發展。據業內專傢調查分析,np技術將嚮着更高的性能、更多功能支持、多種技術並存和標準化等特徵發展,基於np的防火墻産品將隨着np的發展大步前行。
  更高的性能
  五年來,網絡的傳輸速度每年翻一番,幾年前的主幹網速度是155Mb/s,現在已經到了10Gb/s,兩到三年內又會提高到40Gb/s,網絡處理器也必須滿足這種變化。np性能的提高,將直接推動防火墻性能的提高。
  更多的功能支持
  隨着網絡處理器在更多領域中的應用,網絡處理器必須具有更多的功能支持,如深度內容處理和IPV6協議識別,以能適應防火墻等安全設備的需求。
  多種技術並存
  np不是萬能的,它並不會完全取代通用處理器和ASIC在網絡設備中的應用。在對處理性能需求很高的高端設備中,ASIC仍然具有很強的生命力,可以預見的是,在數據層面、控製層面和管理層,通用處理器、np和ASIC將各司其職,共同為防火墻應用提供靈活的服務。
  實現標準化
  np技術的開發與應用直接促成了網絡處理器論壇(npF)的誕生。npF的成立,將進一步推動np的發展,實現標準化,解决産品互連互通和軟件可移植性等問題。
  涌現龐大的第三方開發隊伍
  隨着標準化工作的深入,再加上網絡處理器本身具有模塊化結構的特點,將涌現出一支龐大的第三方隊伍,在硬件組件、np操作係統、開發工具、軟件應用等方面努力。
  總之,防火墻技術與np技術開始緊密地聯繫在一起,np技術的變革將推動防火墻技術嚮着更高性能、更多功能以及標準化的方向發展。
  np經濟含義
  np是Net Profit縮寫,淨利潤(收益)是指在利潤總額中按規定交納了所得稅以後公司的利潤留存,一般也稱為稅後利潤或淨收入。淨利潤的計算公式為:
  淨利潤=利潤總額×(1-所得稅率)
  淨利潤是一個企業經營的最終成果,淨利潤多,企業的經營效益就好;淨利潤少,企業的經營效益就差,它是衡量一個企業經營效益的主要指標。
鎿Neptunium
  元素符號: np 英文名: Neptunium 中文名: 鎿
  在元素周期表中位於鈾(U)和鈈(Pu),同屬於錒係元素
  相對原子質量: 237.048 常見化合價: +3,+4,+5,+6 電負性: 1.36
  外圍電子排布: 5f4 6d1 7s2 核外電子排布: 2,8,18,32,23,8,2
  同位素及放射綫: np-235[1.08y] np-236[155000y] np-236m[22.5h] np-237(放 α[2140000y]) np-238[2.11d] np-239[2.35d] np-240[1.03h] np-240m[7.22m]
  熱容:J /(mol· K)
  29.46
  導熱係數:W/(m·K)
  6.3
  導電性:10^6/(cm ·Ω )
  0.00822
  熔化熱:(千焦/摩爾)
  5.190
  電子親合和能: 0 KJ·mol-1
  第一電離能: 600 KJ·mol-1 第二電離能: 0 KJ·mol-1 第三電離能: 0 KJ·mol-1
  單質密度: 20.45 g/cm3 單質熔點: 640.0 ℃ 單質沸點: 3902.0 ℃
  原子半徑: 0 埃 離子半徑: 埃 共價半徑: 0 埃
  常見化合物: npO2 npF4
  發現人: 麥剋米倫、阿貝爾森 時間: 1940 地點: 美國
  名稱由來:
  得名於海王星的名字“Neptune”。
  元素描述:
  稀有的銀白色放射性金屬。
  元素來源:
  用慢中子轟擊鈾原子而得到。
  元素用途:
  那是現在乏燃料後處理中的重要元素,是Pu-238的主要來源之一。戰略和軍事用途很廣。
NP問題
  P/np問題是在理論信息學中計算復雜度理論領域裏至今沒有解决的問題,它被“剋雷數學研究所”(Clay Mathematics Institute, 簡稱CMI)在千禧年大奬難題中收錄。P/np問題中包含了復雜度類P與np的關係。1971年史提芬·古剋(Stephen A. Cook) 和 Leonid Levin 相對獨立的提出了下面的問題,即是否兩個復雜度類P和np是恆等的(P=np?)。
  P和np
  復雜度類P包含所有那些可以由一個確定型圖靈機在多項式表達的時間內解决的問題;類np由所有其肯定解可以在給定正確信息的多項式時間內驗證的决定問題組成,或者等效的說,那些解可以在非確定圖靈機上在多項式時間內找出的問題的集合。很可能,計算理論最大的未解决問題就是關於這兩類的關係的:
  P和np相等嗎?
  在2002年對於100研究者的調查,61人相信答案是否定的,9個相信答案是肯定的,22個不確定,而8個相信該問題可能和現在所接受的公理獨立,所以不可能證明或證否。 對於正確的解答,有一個,000,000美元的奬勵。
  np-完全問題(或者叫npC)的集合在這個討論中有重大作用,它們可以大致的被描述為那些在np中最不像在P中的。(確切定義細節請參看np-完全)理論計算機科學家現在相信P, np,和npC類之間的關係如圖中所示,其中P和npC類不交。
  假設P ≠ np的復雜度類的圖解.如P = np則三個類相同.本質上,P = np問題問道:如果是/不是問題的正面答案可以很快驗證,其答案是否也可以很快計算?這裏有一個給你找點這個問題的感覺的例子。給定一個大數Y,我們可以問Y是否是復合數。例如,我們可能問53308290611是否有非平凡的因子。回答是肯定的,雖然手工找出一個因子很麻煩。從另一個方面講,如果有人聲稱答案是"對,因為224737可以整除53308290611",則我們可以很快用一個除法來驗證。驗證一個數是除數比首先找出除數來簡單得多。用於驗證一個正面答案所需的信息也稱為證書。所以我們的結論是,給定 正確的證書,問題的正面答案可以很快的(也就是,在多項式時間內)驗證,而這就是這個問題屬於np的原因。雖然這個特定的問題,最近被證明為也在P類中(參看下面的關於"質數在P中"的參考),這一點也不明顯,而且有很多類似的問題相信不屬於類P。
  限製到是/不是問題並沒有改變問題;即使我們允許更復雜的答案,最後的問題(是否FP = Fnp)是等價的。
  形式化定義
  更正式一些,一個决定問題是一個取一些字符串為輸入並要求輸出為是或否的問題。若有一個算法(譬如圖靈機,或一個LISP或Pascal的程序並有無限的內存)能夠在最多nk步內對一個串長度為n的輸入給出正確答案,其中k是某個不依賴於輸入串的常數,則我們稱該問題可以在多項式時間內解决,並且將它置入類P。直觀的講,我們將P中的問題視為可以較快解决的問題。
  現在假設有一個算法A(w,C)取兩個參數,一個串w,也就是我們的决定問題的輸入串,而另一個串C是“建議證明”,並且使得A在最多nk步之內産生“是/否”答案(其中n是w的長度而k不依賴於w)。進一步假設
  w是一個答案為“是”的例子,當且僅當,存在C使得A(w,C)返回“是”。
  則我們稱這個問題可以在非决定性多項式時間內解决,且將它放入np類。我們把算法A作為一個所建議的證明的檢驗器,它運行足夠快。(註意縮寫np代表“Non-deterministic(非確定性)Polynomial(多項式)”而不是代表“Non-Polynomial(非多項式)。)
  np完全
  要解决P = np問題,np完全的概念非常有用。不嚴格的講,np完全問題是np類中“最難”的問題,也就是說它們是最可能不屬於P類的。這是因為任何np中的問題可以在多項式時間內變換成為任何特定np完全問題的一個特例。例如,旅行商問題的判定問題版本是np完全的。所以np中的任何問題的任何特例可以在多項式時間內機械地轉換成旅行商問題的一個特例。所以若旅行商問題被證明為在P內,則P = np!旅行商問題是很多這樣的np完全的問題之一。若任何一個np完全的問題在P內,則可以推出P = np。不幸的是,很多重要的問題被證明為np完全,但沒有一個有已知快速的算法。
  更難的問題
  雖然是否P=np還是未知的,在P之外的問題是已經知道存在的。尋找國際象棋或圍棋最佳走法(在n乘n棋盤上)是指數時間完全的。因為可以證明P ≠ EXPTIME(指數時間),這些問題位於P之外,所以需要比多項式時間更多的時間。判定Presburger算術中的命題是否為真的問題更加睏難。Fischer和Rabin於1974年證明每個决定Presburger命題的真偽性的算法有最少2^(2^(cn))的運行時間,c為某個常數。這裏,n是Presburger命題的長度。因此,該命題已知需要比指數時間更多的運行時間。不可判定問題是更加睏難的,例如停機問題。它們無法在任何給定時間內解决。
  P真的容易處理嗎?
  上面所有的討論假設了P表示“容易”而“不在P中”表示“睏難”。這是一個在復雜度理論中常見而且有一定準確性的假設,它在實踐中卻不總是真的,原因包括如下幾點:
  它忽略了常數因子。一個需要101000n時間的問題是屬於P的(它是綫性時間的),但是事實上完全無法處理。一個需要10-100002n時間的問題不是在P中的(它是指數時間的),但是對於n 取值直到幾千時還是很容易處理的。
  它忽略了指數的大小。一個時間復雜度n1000屬於P,但是很難對付。已經證明在P中存在需要任意大的指數的問題(參看時間等級定理)。一個時間復雜度2n/1000的問題不屬於P,但對與n直到幾千還是容易應對的。
  它衹考慮了最壞情況的復雜度。可能現實世界中的有些問題在多數時候可以在時間n中解决,但是很偶爾你會看到需要時間2n的特例。這個問題可能有一個多項式的平均時間,但最壞情況是指數式的,所以該問題不屬於P。
  它衹考慮確定性解。可能有一個問題你可以很快解决如果你可以接受出現一點誤差的可能,但是確保正確的答案會難得多。這個問題不會屬於P,雖然事實上它可以很快求解。這實際上是解决屬於np而還不知道是否屬於P的問題的一個辦法(參看RP, BPP)。
  新的諸如量子電腦這樣的計算模型,可能可以快速的解决一些尚未知道是否屬於P的問題;但是,沒有一個它們已知能夠解决的問題是np完全的。不過,必須註意到P和np問題的定義是采用象圖靈機這樣的經典計算模型的屬於表述的。所以,即使一個量子計算機算法被發現能夠有效的解决一個np完全問題,我們衹是有了一個快速解决睏難問題的實際方法,而不是數學類P和np相等的證明。
  計算機科學家為什麽認為P ≠ np
  多數計算機科學家相信P≠np。該信念的一個關鍵原因是經過數十年對這些問題的研究,沒有人能夠發現一個np完全問題的多項式時間算法。而且,人們早在np完全的概念出現前就開始尋求這些算法了(Karp的21個np完全問題,在最早發現的一批中,有所有著名的已經存在的問題]])。進一步地,P = np這樣的結果會導出很多驚人的結果,那些結果現在被相信是不成立的,例如np = np和P = PH。
  也有這樣論證的:問題較難求解(np)但容易驗證(P),這和我們日常經驗是相符的。
  從另一方面講,某些研究者認為我們過於相信P ≠ np,而應該也去尋找P = np的證明。例如,2002年中有這樣的聲明:
  傾嚮P≠np的主要論據是在窮盡搜索的領域完全沒有本質進展。也就是說,以我的觀點,一個很弱的論據。算法的空間是很大的,而我們衹是在開始探索的起點。[ . . . ] 費馬最後定理的解决也顯示非常簡單的[sic]問題可能衹有用非常深刻的理論才能解决。
  — Moshe Vardi,萊斯大學
  過分依賴某種投機不是規劃研究的一個好的導引。我們必須總是嘗試每個問題的兩個方向。偏見可能導致著名的數學家無法解决答案和他們的預計相反的著名問題,雖然他們發展了所有所需的方法。
  — Anil Nerode, 康奈爾大學
  關於證明的難度的結果
  雖然百萬美元的奬金和大量投入巨大卻沒有實質性結果的研究足以顯示該問題是睏難的,還有一些形式化的結果證明為什麽該問題可能很難解决。
  最常被引用的結果之一設計神喻。假想你有一個魔法機器可以解决單個問題,例如决定一個給定的數字是否為質數,但可以瞬間解决這個問題。我們的新問題是,若我們被允許任意利用這個機器,是否存在我們可以在多項式時間內驗證但無法在多項式時間內解决的問題?結果是,依賴於機器能解决的問題,P = np和P ≠ np二者都可以證明。這個結論的後果是,任何可以修改來證明該機器的存在性的結果不能解决問題。不幸的是,幾乎所有經典的方法和大部分已知的方法可以這樣修改(我們稱它們在相對化)。
  如果這還不算太糟的話,1993年Razborov和Rudich證明的一個結果表明,給定一個特定的可信的假設,在某種意義下“自然”的證明不能解决P = np問題。 這表明一些現在似乎最有希望的方法不太可能成功。隨着更多這類的定理得到證明,該定理的可能證明有越來越多的陷阱要規避。
  這實際上也是為什麽np完全問題有用的原因:若有一個多項式時間算法,或者沒有一個這樣的算法,對於np完全問題存在,這將用一種相信不被上述結果排除在外的方法來解决P = np問題。
  多項式時間算法
  沒人知道多項式時間算法對於np完全問題是否存在。但是如果這樣的算法存在,我們已經知道其中的一些了!例如,下面的算法正確的接受了一個np完全語言,但是沒人知道通常它需要多久運行。它是一個多項式時間算法當且僅當P = np
  // 接受np完全語言的一個算法子集和。
  //
  // 這是一個多項式時間算法當且僅當P=np
  //
  // “多項式時間”表示它在多項式時間內返回“是”,若
  // 結果是“是”,否則永遠運行。
  //
  // 輸入:S = 一個自然數的有限集
  // 輸出:"是" 如果某個S的子集加起來等於0。
  // 否則,它永遠運行沒有輸出。
  // 註意: "程序數P" 是你將一個整數P寫為二進製,然後
  // 將位串考慮為一個程序。
  // 每個可能的程序都可以這樣産生,
  // 雖然多數什麽也不做因為有語法錯誤。
  //
  FOR N = 1...infinity
  FOR P = 1...N
  以S為輸入運行程序數P N步
  IF 程序輸出一個不同的整數的列表
  AND 所有整數都在S中
  AND 整數的和為0
  THEN
  OUTPUT "是" 停機
  若P = np,則這是一個接受一個np完全語言的多項式時間算法。“接受”表示它在多項式時間內給出“是”的答案,但允許在答案是“否”的時候永遠運行。
  可能我們想要“解决”子集和問題,而不是僅僅“接受”子集和語言。這表示我們想要它總是停機並返回一個“是”或“否”的答案。是否存在任何可能在多項式時間內解决這個問題的算法?沒有人知道。但是如果這樣的算法存在,那麽我們已經知道其中的一些了!衹要將上面的算法中的IF語句替換成下面的語句:
  IF 程序輸出一個完整的數學證明
  AND 證明的每一步合法
  AND 結論是S確實有(或者沒有)一個和為0的子集
  THEN
  OUTPUT "是" (或者"不是"如果那被證明了)並停機
  邏輯表述
  P=np問題可以用邏輯命題的特定類的可表達性的術語來重新表述。所有P中的語言可以用一階邏輯加上最小不動點操作(實際上,這允許了遞歸函數的定義)來表達。類似地,np是可以用存在性二階邏輯來表達—也就是,在關係、函數、和子集上排除了全域量詞的二階邏輯。多項式等級,PH中的語言對應與所有的二階邏輯。這樣,“P是np的真子集嗎”這樣的問題可以表述為“是否存在性二階邏輯能夠表達帶最小不動點操作的一階邏輯的所不能表達的語言?”
  花絮
  普林斯頓大學計算機係樓將二進製代碼表述的“P=np?”問題刻進頂樓西面的磚頭上。如果證明了P=np,磚頭可以很方便的換成表示“P=np!”。
  康奈爾大學的Hubert Chen博士提供了這個玩笑式的P不等於np的證明:“反證法。設P = np。令y為一個P = np的證明。證明y可以用一個合格的計算機科學家在多項式時間內驗證,我們認定這樣的科學家的存在性為真。但是,因為P = np,該證明y可以在多項式時間內由這樣的科學家發現。但是這樣的發現還沒有發生(雖然這樣的科學家試圖發現這樣的一個證明),我們得到矛盾。
NP在遊戲中
  在一些遊戲當中。
  一些玩傢會嚮對方輸入np。NO problem意思是沒關係。
  在街頭籃球遊戲中,NICE PASS的縮寫.
語言學研究常用術語NP
  np的意思是名詞性成分,應該是Nominal(名詞性的)和Part(部分)的省稱,名詞性成分包括名詞和名詞性的短語。與之相關的一個詞是VP,意思當然是動詞性成分了,包括動詞和動詞性短語。如有篇語言學論文題目是《確定"S+VP+的(+np)"結構中"的"字歸屬之我見》。如果詞語解釋有誤,希望知者斧正,因為目前網上和詞典還找不到這兩詞的精確解釋,大學問傢又不肯站出來說話,因此我衹能拋磚引玉了。
NP—>netwok provider
  np者netwok provider也,即網絡提供商
  BTW
  network operator 可以包含電信運營商的網絡運營商
   netwok provider指網絡提供商
  不管是固定網絡運營商、移動網絡運營商還是電纜網絡運營商,都面臨着多方力量在重塑行業格局。隨着競爭不斷加劇,運營商的重點是以成本效益和資源效率最高的方式提供優質服務和應用。同時,固定網絡、移動網絡和IP網絡正在融合,在接入應用的地點和方式方面為最終用戶提供了最大的靈活性。
  這在管理和監測網絡方面給網絡運營商帶來了某些獨特的挑戰。網絡運營商不僅需要從網絡角度知道網絡運行狀況,還需要從服務角度知道網絡運行狀況。此外,他們需要在提供多媒體服務和應用時有效利用網絡資源。
NP有生態學中的定義
  net primary production淨初級生産量或簡稱npP
  生態係統能量流動的來源於植物光合作用對太陽能的固定。植物所固定的太陽能或製造的有機物質稱為初級生産量或第一性生産量(primary production)。
  在初級生産中,植物固定的能量有一部分被植物自己的呼吸消耗掉,剩下的可用於植物生長和繁殖,這一部分稱為淨初級生産量。而包括呼吸消耗(R)的全部生産量稱為總初級生産量(GP或GPP)。
  三者之間的關係為:np=GP-R
其他含義
  中國福建省南平市的拼音首字母
  np.
  在同人文或者女尊文、耽美文中的np表示的是N配
  也就是一個女/男主角(男主角)和多個異性(或同性)産生曖昧,或雙方喜歡交往。
  在耽美小說中,既是一攻多受 或一受多攻的意思
  np
  Nippon (立邦)立邦油漆的行業簡寫。
  np-n
  壬基酚與環氧乙烷加成物
相關詞
穿越架空言情技術多媒體諾亞舟學習機尊卑