Low (complexity)
http://dbpedia.org/resource/Low_(complexity)
在計算複雜度理論內，若有A與B兩個複雜度類，且AB = A；或者說, A 在B成為他的神諭之後的複雜度等同於A，則我們說複雜度類別B比A要來的"低"。這陳述代表著一個可以解決問題類別A的機器，在獲得了在單位時間內解決問題類別B的能力之後，並沒有增加多餘的計算能力。特別是，這代表著如果B類別低於A類別，則B必然包含在A裡面。 較不正式的說，較低的關係不僅僅代表包含於B的問題可以被能夠解決A問題的機器所解決, 而且是"可以被簡單解決的"。一個能解決A問題類別的機器可以模擬許多計算B的啟示，而不超出其計算能力的上限值。 建立在一個類別低於另一類別的關係跟結果常常被稱呼為"lowness results"。
rdf:langString
In computational complexity theory, a language B (or a complexity class B) is said to be low for a complexity class A (with some reasonable relativized version of A) if AB = A; that is, A with an oracle for B is equal to A. Such a statement implies that an abstract machine which solves problems in A achieves no additional power if it is given the ability to solve problems in B at unit cost. In particular, this means that if B is low for A then B is contained in A. Informally, lowness means that problems in B are not only solvable by machines which can solve problems in A, but are “easy to solve”. An A machine can simulate many oracle queries to B without exceeding its resource bounds.
rdf:langString
rdf:langString
Low (complexity)
rdf:langString
低 (複雜度)
xsd:integer
2006468
xsd:integer
1050436176
rdf:langString
In computational complexity theory, a language B (or a complexity class B) is said to be low for a complexity class A (with some reasonable relativized version of A) if AB = A; that is, A with an oracle for B is equal to A. Such a statement implies that an abstract machine which solves problems in A achieves no additional power if it is given the ability to solve problems in B at unit cost. In particular, this means that if B is low for A then B is contained in A. Informally, lowness means that problems in B are not only solvable by machines which can solve problems in A, but are “easy to solve”. An A machine can simulate many oracle queries to B without exceeding its resource bounds. Results and relationships that establish one class as low for another are often called lowness results. The set of languages low for a complexity class A is denoted Low(A).
rdf:langString
在計算複雜度理論內，若有A與B兩個複雜度類，且AB = A；或者說, A 在B成為他的神諭之後的複雜度等同於A，則我們說複雜度類別B比A要來的"低"。這陳述代表著一個可以解決問題類別A的機器，在獲得了在單位時間內解決問題類別B的能力之後，並沒有增加多餘的計算能力。特別是，這代表著如果B類別低於A類別，則B必然包含在A裡面。 較不正式的說，較低的關係不僅僅代表包含於B的問題可以被能夠解決A問題的機器所解決, 而且是"可以被簡單解決的"。一個能解決A問題類別的機器可以模擬許多計算B的啟示，而不超出其計算能力的上限值。 建立在一個類別低於另一類別的關係跟結果常常被稱呼為"lowness results"。
xsd:nonNegativeInteger
7282