| dbo:abstract |
In computational complexity theory of computer science, the structural complexity theory or simply structural complexity is the study of complexity classes, rather than computational complexity of individual problems and algorithms. It involves the research of both internal structures of various complexity classes and the relations between different complexity classes. (en) Em Complexidade computacional da ciência da computação, a teoria da complexidade estrutural ou simplesmente complexidade estrutural é o estudo de classes de complexidade, ao invés da complexidade computacional de problemas individuais e algoritmos. Ela envolve a investigação tanto das estruturas internas de várias classes de complexidade quanto das relações entre as diferentes classes de complexidade. (pt) 在計算複雜度理論內，結構複雜度理論（英語：structural complexity theory)或者簡單的結構複雜度（英語：structural complexity)是專門研究複雜度類本身，而非單一問題的可計算性或演算法的學問。這理論牽涉到研究各種複雜度類的內部結構以及不同複雜度類之間的關係。 這理論的出現，是在解決這類問題中第一個，也仍是最重要的一個問題：P/NP問題時，不斷失敗的一個結果。許多這方面的研究都基於 P != NP這個假設，以及一個更深遠的推測：內的複雜度類個數是無限的。 這個領域的一些主要研究方向有： * 各種未解的問題，對複雜度類之間關係所產生的影響。 * 各種限制資源的歸約方式以及相對應的完全語言。 * 各種對於讀取跟儲存資料的限制以及使用方法，會對複雜度類產生的影響。 (zh) |
| dbo:thumbnail |
wiki-commons:Special:FilePath/Polynomial_time_hierarchy.svg?width=300 |
| dbo:wikiPageID |
20188597 (xsd:integer) |
| dbo:wikiPageLength |
5913 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1106803357 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:NP_(complexity) dbr:Bounded-error_probabilistic_polynomial dbr:Decision_problem dbr:Space_hierarchy_theorem dbr:Computable_function dbr:Valiant–Vazirani_theorem dbr:Seinosuke_Toda dbr:NL_(complexity) dbc:Structural_complexity_theory dbr:Leslie_Valiant dbr:Complexity_class dbr:Compression_theorem dbr:Computational_complexity_theory dbr:Computer_science dbr:PH_(complexity) dbr:P_(complexity) dbr:Padding_argument dbr:Theoretical_computer_science dbr:Walter_Savitch dbr:Gödel_Prize dbr:Linear_bounded_automaton dbr:Isolation_lemma dbr:Reduction_(complexity) dbr:Toda's_theorem dbr:Boolean_satisfiability_problem dbr:Polynomial_hierarchy dbr:RP_(complexity) dbr:Neil_Immerman dbr:Turing_machine dbr:Vijay_Vazirani dbr:Immerman–Szelepcsényi_theorem dbr:Róbert_Szelepcsényi dbr:NSPACE dbr:Time_hierarchy_theorem dbr:Savitch's_theorem dbr:Sipser–Lautemann_theorem dbr:Space_complexity dbr:P_=_NP_problem dbr:Polynomial_time_hierarchy dbr:Deterministic_Turing_machine dbr:File:Polynomial_time_hierarchy.svg dbr:Complete_language |
| dbp:wikiPageUsesTemplate |
dbt:About dbt:Citation_needed dbt:Main dbt:Reflist |
| dct:subject |
dbc:Structural_complexity_theory |
| rdfs:comment |
In computational complexity theory of computer science, the structural complexity theory or simply structural complexity is the study of complexity classes, rather than computational complexity of individual problems and algorithms. It involves the research of both internal structures of various complexity classes and the relations between different complexity classes. (en) Em Complexidade computacional da ciência da computação, a teoria da complexidade estrutural ou simplesmente complexidade estrutural é o estudo de classes de complexidade, ao invés da complexidade computacional de problemas individuais e algoritmos. Ela envolve a investigação tanto das estruturas internas de várias classes de complexidade quanto das relações entre as diferentes classes de complexidade. (pt) 在計算複雜度理論內，結構複雜度理論（英語：structural complexity theory)或者簡單的結構複雜度（英語：structural complexity)是專門研究複雜度類本身，而非單一問題的可計算性或演算法的學問。這理論牽涉到研究各種複雜度類的內部結構以及不同複雜度類之間的關係。 這理論的出現，是在解決這類問題中第一個，也仍是最重要的一個問題：P/NP問題時，不斷失敗的一個結果。許多這方面的研究都基於 P != NP這個假設，以及一個更深遠的推測：內的複雜度類個數是無限的。 這個領域的一些主要研究方向有： * 各種未解的問題，對複雜度類之間關係所產生的影響。 * 各種限制資源的歸約方式以及相對應的完全語言。 * 各種對於讀取跟儲存資料的限制以及使用方法，會對複雜度類產生的影響。 (zh) |
| rdfs:label |
Structural complexity theory (en) Teoria da complexidade estrutural (pt) 結構複雜度理論 (zh) |
| owl:sameAs |
freebase:Structural complexity theory wikidata:Structural complexity theory dbpedia-pt:Structural complexity theory dbpedia-zh:Structural complexity theory https://global.dbpedia.org/id/4vHXm |
| prov:wasDerivedFrom |
wikipedia-en:Structural_complexity_theory?oldid=1106803357&ns=0 |
| foaf:depiction |
wiki-commons:Special:FilePath/Polynomial_time_hierarchy.svg |
| foaf:isPrimaryTopicOf |
wikipedia-en:Structural_complexity_theory |
| is dbo:knownFor of |
dbr:Alan_Selman |
| is dbo:wikiPageRedirects of |
dbr:Structural_complexity dbr:Structural_computational_complexity |
| is dbo:wikiPageWikiLink of |
dbr:Berman–Hartmanis_conjecture dbr:MAXEkSAT dbr:Complexity_and_Real_Computation dbr:Computational_complexity_theory dbr:Alan_Selman dbr:Uwe_Schöning dbr:List_of_theorems dbr:Structural_complexity dbr:Structural_computational_complexity |
| is dbp:knownFor of |
dbr:Alan_Selman |
| is foaf:primaryTopic of |
wikipedia-en:Structural_complexity_theory |
