完备性和決定性問題

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

完备性和決定性問題之间的区别

完备性 vs. 決定性問題

在数学及其相关领域中，一个对象具有完备性，即它不需要添加任何其他元素，这个对象也可称为完备的或完全的。更精确地，可以从多个不同的角度来描述这个定义，同时可以引入完备化这个概念。但是在不同的领域中，“完备”也有不同的含义，特别是在某些领域中，“完备化”的过程并不称为“完备化”，另有其他的表述，请参考代数闭域、紧化或哥德尔不完备定理。. 在可計算性理論與計算複雜性理論中，所謂的決定性問題（Decision problem）是一個在某些形式系統回答是或否的問題。例如：「給兩個數字x與y，x是否可以整除y？」便是決定性問題，此問題可回答是或否，且依據其x與y的值。 決定性問題與功能性問題（Function problem，或複雜型問題）密切相關，功能性問題的答案內容，較簡單的是與非複雜許多。範例問題：「給予一個正整數x，則哪些數可整除x？」 另一個與上述兩類問題相關的是最佳化問題（Optimization problem），此問題關心的是尋找特定問題的最佳答案。 解決決定性問題的方法稱為決策程式或演算法。一個針對決定性問題的演算法將說明給予參數x和y的情況下如何決定x是否整除y。若是某些決定性問題可以被一些演算法所解決，則稱此問題可決定。 計算複雜度的領域中，分類可決定問題的依據在於此問題有多難被解決。在此標準下，所謂的難是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞迴理論中，非決定性問題由圖靈度決定，指的是一種在任何解答中隱含的不可計算性量詞。 計算性理論的研究集中在決定性問題上。在與功能性問題的等值問題中，並沒有失去其普遍性。.

子集

子集，為某個集合中一部分的集合，故亦稱部分集合。 若A和B为集合，且A的所有元素都是B的元素，则有：.

子集和完备性 · 子集和決定性問題 · 查看更多 »

完備 (複雜度)

在計算複雜性理論內，一個計算問題(computational problem)對一個複雜度類是完備或者完全的，用比較不正式的解釋，是說這問題在此複雜度類裡面是一個"最難的"或者"最代表性的"題目。如果一個問題的解法可以允許你快速解決這個複雜度類的其他問題的話，我們說這問題對此類別是難(hard)的題目。 更正式的說法是，如果在一個給定的歸約方式之下，所有複雜度類 C裡面的問題都存在某種歸約方式，可以歸約到某個問題p，我們說這個問題p 是C的難問題。如果一個問題是此類別的，且本身是這個類別裡面的一員，則這個問題就是對這個複雜度類完備的(在給定的歸約條件之下)。 一個問題如果對複雜度類C是完備的話，我們會說這個問題是C-完備或者C完全(C-complete)的問題，至於這一些對C是完備問題的集合我們也稱為C-完備。 第一個且是最有名的是NP完全：一個包含許多實際但是不容易的題目。相同的，我們習慣用C難(C-hard)這種用詞稱呼包含所有C難(C-hard)的問題，例如說，NP難。 正常來說我們都假設歸約過程在計算複雜度上面不會比起問題本身要難。因此之故，如果我們對一個C-完備問題有"計算上簡單"的解法的話，則所有在"C"這類別裡面的問題都有"簡單"的解法。 一般說來，有遞歸可枚舉(recursive enumeration)的複雜度類都會有已知的完備問題，而並非如此的類別則沒有已知的完備問題。舉例來說，NP，反NP，PLS，PPA 都有已知的完備問題，而RP，ZPP，BPP和TFNP則沒有已知的完備問題(雖然這不代表未來不會發現完備問題)。 有一些複雜度類是沒有完備問題存在的。舉例來說，Sipser證明了存在一個語言M令BPPM (BPP加上一個M的諭示) 是沒有完備問題的。.

完備 (複雜度)和完备性 · 完備 (複雜度)和決定性問題 · 查看更多 »

形式语言

在数学、逻辑和计算机科学中，形式语言（Formal language）是用精确的数学或机器可处理的公式定义的语言。 如语言学中语言一样，形式语言一般有两个方面: 语法和语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论，它只研究语言的语法而不致力于它的语义。在形式语言理论中，形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。.

完备性和形式语言 · 形式语言和決定性問題 · 查看更多 »

計算複雜性理論

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

完备性和計算複雜性理論 · 決定性問題和計算複雜性理論 · 查看更多 »