P/NP问题和游戏复杂度

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

P/NP问题和游戏复杂度之间的区别

P/NP问题 vs. 游戏复杂度

P/NP问题是在理论信息学中计算复杂度理论领域里至今未被解决的问题，也是克雷数学研究所七个千禧年大奖难题之一。P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克（Stephen A. Cook）和相对独立地提出了下面的问题，即复杂度类P和NP是否是恒等的（P. 游戏复杂度（game complexity）可以用许多方法加以衡量。本条目讲述其中的5種方法：状态空间复杂度（state-space complexity）、游戏树的大小（game tree size）、策略复杂度（decision complexity）、博弈树复杂度（game-tree complexity）與计算复杂度（computational complexity）。.

复杂性类

在計算複雜度理論中，一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下--： 例如'''NP'''類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題（Function problem）的集合，例如'''FP'''。 許多複雜度類可被描述它的數學邏輯（mathematical logic）特徵化，請見可描述的複雜度（descriptive complexity）。 而Blum公理用於不需實際計算模型就可定義複雜度類的情況。.

P/NP问题和复杂性类 · 复杂性类和游戏复杂度 · 查看更多 »

國際象棋

國際象棋（chess），又稱歐洲象棋或--，是一種二人對弈的戰略棋盘遊戲，也是世界上最流行的遊戲之一。世界各地數以百萬計的人在家中、中、網路上以或比賽形式对弈。 國際象棋的棋盤由64個黑白相間的八乘八網格組成。每位玩家开局时各有16個棋子：一王、一-后-、兩车、兩马、兩象和八兵，各具不同功能与走法。棋手行棋目标是將對方的王處在不可避免的威脅之下以將死對方，也可以通过對方自知无望、主动认输而獲勝，另有相当多的情况可导致和局。遊戲過程分三個階段：开局、中局、，共有1043至1050種棋局變化。 国际象棋棋子多用木或塑膠製成，也有用石材制作；较为精美的石頭、玻璃（水晶）或金屬製棋子常用作裝飾擺設。.

P/NP问题和國際象棋 · 國際象棋和游戏复杂度 · 查看更多 »

围棋

围棋是一種策略性棋類，使用格狀棋盤及黑白二色棋子進行對弈。起源于中国，中國古时有“弈”、“--”、“手谈”等多种称谓，屬琴棋书画四艺之一。西方稱之為“Go”，是源自日語「碁」的发音。 对弈双方在棋盘网格的交叉点上交替放置黑色和白色的棋子。Matthews, Charles.

P/NP问题和围棋 · 围棋和游戏复杂度 · 查看更多 »

計算複雜性理論

计算复杂性理论（Computational complexity theory）是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。 如果一个问题的求解需要相当多的资源（无论用什么算法），则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源（时间和空间），从而将资源的确定方法正式化了。其他复杂性测度同样被运用，比如通信量（应用于通信复杂性），电路中门的数量（应用于电路复杂性）以及中央处理器的数量（应用于并行计算）。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。 在理论计算机科学领域，与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量，而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说，它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地，在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标：后者关心的是何种问题原则上可以用算法解决。.

P/NP问题和計算複雜性理論 · 游戏复杂度和計算複雜性理論 · 查看更多 »