| http://dbpedia.org/ontology/abstract
|
在計算複雜度理論中，一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下形式： 可以被同一個抽象機器M使用O(f(n))的資源R所解決的問題的集合（n是輸入資料的大小）。 例如NP類別就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類別則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題的集合，例如。 許多複雜度類可為數學邏輯所描述刻劃，請見。 布盧姆複雜度則不需實際抽象機器就可定義複雜度類。
, Nella teoria della complessità computazion … Nella teoria della complessità computazionale, una classe di complessità è un insieme di problemi di una certa complessità. Un esempio tipico di definizione di classe di complessità ha la forma: l'insieme di problemi che, se esiste la soluzione, possono essere risolti da una macchina astratta M usando della risorsa R, con dimensione dell'input Ad esempio, la classe NP è l'insieme dei problemi di decisione che possono essere risolti da una macchina di Turing non deterministica in tempo polinomiale, mentre la classe P è l'insieme dei problemi di decisione che possono essere risolti da una macchina di Turing deterministica in tempo polinomiale. Alcune classi di complessità sono insiemi di problemi costruttivi (cioè che richiedono di calcolare una funzione, e non di rispondere SÌ o NO), come ad esempio . Molte classi di complessità possono essere caratterizzate in termini della logica matematica necessaria ad esprimerle; vedi . Gli possono essere usati per definire classi di complessità senza riferirsi ad un concreto.omplessità senza riferirsi ad un concreto.
, في علم التعقيد الحسابي، قسم تعقيد هي مجموع … في علم التعقيد الحسابي، قسم تعقيد هي مجموعة من المسائل المُتعلقة بالاساس فيما بينها بمورد مُعين، اغلب الاقسام لديها التعريف التالي: مجموعة المسائل التي يمكن حلها بواسطة موارد حيث أنَّ n هو طول المُدخل. على سبيل المثال: القسم NP هو مجموعة المسائل التي يمكن حلها بوقت حدودي (أي ) بواسطة آلة تيورنج غير حتمية، مثال آخر هو القسم بيسبايس وهو مجموعة المسائل التي يمكن حلها بواسطة آلة تيورنج حتمية وتستخدم مكان اضافي طوله حدودي (أي انها تسخدم مكان اضافي). الاقسام الأساسية مُعرفة حسب المتغيرات التالية: 1.
* نوع المسألة الحسابية: على الاغلب المسائل هي مسائل تقرير (decision problem), ولكن اقسام التعقيد يمكن تعريفها أيضا بواسطة مسائل دوال (function problem) مثل القسم FP أو مسائل عد (counting problem) مثل P# أو مسائل استمثال... 2.
* نوع نموذج الحساب: على الاغلب نموذج الحساب هو آلة تيورنج الحتمية ولكن العديد من الاقسام تُعرف بالة تيورنج غير حتمية، دوائر بوليانية، آلة تيورنج كمومية... 3.
* المورد الذي يتم تحديده والحدود: مثل «وقت حدودي», «مكان حدودي», «وقت لوجارثمي», ... بعض الاقسام يمكن تشخيصها بواسطة المنطق الرياضي اللازم لتعريفها.صها بواسطة المنطق الرياضي اللازم لتعريفها.
, En teoria de complexitat, una classe de co … En teoria de complexitat, una classe de complexitat és un conjunt de problemes de decisió de complexitat relacionada. Una classe de complexitat típica té una definició de la forma: El conjunt de problemes que se poden resoldre per una màquina abstracta M usant O (f(n)) del recurs R on n és la mida de l'entrada. Les classes de complexitat estan relacionades amb la taxa de creixement de la necessitat de recursos a mesura que augmenta l'entrada n. És una mesura abstracta i no dona uns requeriments de temps o espai en termes de segons o bytes, ja que per obtenir-los caldria tenir informació de la implementació concreta. La funció dins de l'expressió O(...) pot ser una constant, per algorismes que no els afecta la mida n, o una expressió amb un logaritme, una potència d'n com una expressió polinomial o moltes d'altres. La O es llegeix com "d'ordre ". Pel propòsit de teoria de la complexitat, alguns detalls de la funció es poden ignorar, per exemple diferents expressions polinomials es poden ajuntar en una sola classe. El recurs en qüestió pot ser temps, essencialment el nombre d'operacions bàsiques que ha de realitzar una màquina abstracta o espai (emmagatzemament). Per exemple, la classe NP és el conjunt de problemes de decisió les solucions dels quals es poden comprovar per una màquina de Turing no determinista en un temps polinomial, mentre que la classe PSPACE és el conjunt de problemes que es poden solucionar per una màquina de Turing determinista en un espai polinomial.uring determinista en un espai polinomial.
, 複雑性クラス（ふくざつせいクラス、英: Complexity class）は、計算複 … 複雑性クラス（ふくざつせいクラス、英: Complexity class）は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。 抽象機械 M によりO(f(n))の計算資源 R を使って解く事が出来る問題の集合（nは入力長） 例えば、クラスNPは非決定性チューリングマシンで多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEはチューリングマシンでで解く事が出来る決定問題の集合である。ここで、領域とは、実世界ではメモリ空間、チューリングマシンではテープの長さと考えればよい。一部の複雑性クラスは函数問題の集合である（例えば）。 数理論理学では表現の必要に応じて多数の複雑性クラスが定義される（記述計算量）。 ブラムの公理を使うと、完全な計算模型を参照しなくとも複雑性クラスを定義できる。）。 ブラムの公理を使うと、完全な計算模型を参照しなくとも複雑性クラスを定義できる。
, Na Teoria da Complexidade Computacional, u … Na Teoria da Complexidade Computacional, uma Classe de Complexidade é um conjunto de problemas relacionados aos recursos computacionais baseados em complexidade. Uma típica classe de complexidade é definida da seguinte forma: O conjunto de problemas que podem ser resolvidos por uma máquina abstrata M usando O(f(n)) de recurso R, onde n é o tamanho da entrada. Por exemplo, a classe NP é o conjunto de problemas decidíveis que podem ser resolvidos por uma Máquina de Turing Não-Determinística em tempo polinomial, onde a classe PSPACE é o conjunto de problemas decidíveis que podem ser resolvidos por uma Máquina de Turing Determinística em espaço polinomial. As mais simples classes de complexidade são definidas pelos seguintes fatores:
* O tipo de problema computacional: os mais comumentes usados são o problemas de decisão. Contudo, classes de complexidade podem ser definidas baseadas nos problemas funcionais (Um exemplo é o conjunto FP), problemas de contagem (Ex. #P), problemas de otimização, problemas de promessa, etc.
* O modelo de computação: o modelo de computação mais comum é a Máquina de Turing Determinística, porém, muitas classes de complexidade são baseadas em Máquinas de Turing Não-Determiníticas, circuitos booleanos, Máquina de Turing Quântica, circuitos monótonos, etc.
* O(s) recurso(s) que está(ão) sendo limitado(os) e os limites: Estas duas propriedades são usualmente declaradas juntas, assim como "tempo polinomial", "espaço logarítmico", "constante de profundidade", etc. Muitas classes de complexidade podem ser caracterizadas em termos da matemática lógica, necessária para expressá-las. Delimitar o tempo computacional por cima por alguma função concreta f(n) muitas vezes produz classes de complexidade que dependem da escolha do modelo da máquina. Por exemplo, a linguagem {xx| x é uma cadeia binária} pode ser decidida em tempo linear numa Máquina de Turing Multi-Fita, mas necessariamente requer um tempo exponencial no modelo da Máquina de Turing de fita simples. Se nós permitirmos um variação polinomial em tempo de execução, a tese de Cobham-Edmonds afirma que, "as complexidades de tempo em dois modelos razoáveis e gerais são polinomialmente relacionados" (Goldreich 2008, Capítulo 1.2). Esti forma a base da classe de complexidade P, a qual é o conjunto de problemas resolvidos por uma Máquina de Turing Determinística dentro de um tempo polinomial. O conjunto correspondente de problemas funcionais para P é FP. Os axiomas de Blum podem ser usados para definir classes de complexidade sem se referir a um modelo computacional concreto.eferir a um modelo computacional concreto.
, Klasa złożoności – zbiór problemów oblicze … Klasa złożoności – zbiór problemów obliczeniowych o podobnej złożoności obliczeniowej. Najbardziej pospolitą definicją klasy złożoności jest: Zbiór problemów, które mogą być rozwiązane na M przy użyciu O(f(n)) zasobu R, gdzie n jest rozmiarem wejścia. Na przykład klasa P to zbiór problemów decyzyjnych, które można rozwiązać na maszynie Turinga w czasie wielomianowym natomiast klasa NP to zbiór problemów decyzyjnych, które można rozwiązać na niedeterministycznej maszynie Turinga w czasie wielomianowym. Z kolei klasa to zbiór problemów decyzyjnych, które można rozwiązać na równoległej maszynie RAM w czasie polilogarytmicznym przy użyciu wielomianowej liczby procesorów, a to klasa problemów, dla których istnieje działająca w czasie wielomianowym, która zwraca „nie” zawsze, kiedy prawidłową odpowiedzią jest „nie”, i zwraca „tak” (z prawdopodobieństwem, które dla żadnych danych nie spada poniżej pewnej wartości) lub „nie”, kiedy prawidłową odpowiedzią jest „tak””, kiedy prawidłową odpowiedzią jest „tak”
, En teoría de la complejidad computacional, una clase de complejidad es un conjunto de problemas de decisión de complejidad relacionada. Una clase de complejidad tiene una definición de la forma:
, 복잡도 종류(複雜度 種類)는 계산 복잡도 이론에서 에 따라서 문제를 분류한 것이다. 복잡도 종류의 일반적 정의는 다음과 같은 형태로 되어 있다. 예를 들어, NP는 확률적 튜링 기계가 다항시간에 풀 수 있는 판정 문제의 집합이고 PSPACE는 결정론적 튜링 기계가 다항공간에 풀 수 있는 판정 문제의 집합이다. 함수 문제의 집합인 같은 것도 있다. 구체적인 없이 복잡도 종류를 정의하는 데 사용할 수 있는 도 있다.
, In computational complexity theory, a comp … In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements. For instance, the class P is the set of decision problems solvable by a deterministic Turing machine in polynomial time. There are, however, many complexity classes defined in terms of other types of problems (e.g. counting problems and function problems) and using other models of computation (e.g. probabilistic Turing machines, interactive proof systems, Boolean circuits, and quantum computers). The study of the relationships between complexity classes is a major area of research in theoretical computer science. There are often general hierarchies of complexity classes; for example, it is known that a number of fundamental time and space complexity classes relate to each other in the following way: NL⊆P⊆NP⊆PSPACE⊆EXPTIME⊆EXPSPACE (where ⊆ denotes the subset relation). However, many relationships are not yet known; for example, one of the most famous open problems in computer science concerns whether P equals NP. The relationships between classes often answer questions about the fundamental nature of computation. The P versus NP problem, for instance, is directly related to questions of whether nondeterminism adds any computational power to computers and whether problems having solutions that can be quickly checked for correctness can also be quickly solved.or correctness can also be quickly solved.
, Komplexitetsklass är inom komplexitetsteor … Komplexitetsklass är inom komplexitetsteori en mängd beräkningsproblem som har liknande resursbaserad komplexitet. En typisk komplexitetsklass har en definition likt: mängden av alla problem som kan lösas av en M med O(f(n)) mycket resurser R, där n är storleken på problemet. Till exempel är problem av komplexitetsklass NP de beslutsproblem som en icke-deterministisk turingmaskin kan lösa på polynomiell tid, medan klassen PSPACE är mängden av beslutsproblem som kan lösas av en deterministisk turingmaskin på polynomiellt utrymme. Enklare komplexitetsklasser definieras av tre faktorer:
* Problemtypen. Den vanligaste typen är beslutsproblem, men komplexitetsklassen kan även definieras av funktionsproblem (till exempel optimeringsproblem).
* Beräkningsmodell. Den vanligaste beräkningsmodellen är med en deterministisk turingmaskin, men de kan även definieras av icke-deterministiska turingmaskiner, booleska kretsar och kvantturingmaskiner.
* Den begränsade resursen och begränsningarna. Exempel är "polynomiell tid" och "logaritmiskt utrymme". Många komplexitetsklasser kan karaktäriseras med den matematiska logik som krävs för att uttrycka dem.iska logik som krävs för att uttrycka dem.
, De complexiteitsgraad van een bepaald algoritme is de manier waarop dat algoritme zich gedraagt als de grootte van het op te lossen probleem toeneemt.
, En informatique théorique, et plus précisé … En informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace. On peut par exemple citer les classes P et NP.eut par exemple citer les classes P et NP.
, In der Komplexitätstheorie werden Probleme … In der Komplexitätstheorie werden Probleme oder Algorithmen darauf untersucht, wie aufwendig sie zu berechnen sind bezüglich einer bestimmten Ressource, meist bezüglich des Zeitaufwands oder des (Speicher-)Platzaufwands. Bei Problemen wird dabei stets das „kostengünstigste“ Lösungsverfahren angenommen. Der Aufwand ist im Allgemeinen abhängig von der „Größe“ der Eingabe, wie viele Elemente sie umfasst. Abgeschätzt wird der asymptotische Aufwand, also für sehr viele Eingabeelemente. Dabei zeigt sich, dass die Probleme bzgl. ihres Aufwands Gruppen bilden, deren Aufwand für große Eingabemengen auf ähnliche Weise anwächst; diese Gruppen werden Komplexitätsklassen genannt. Eine Komplexitätsklasse ist eine Menge von Problemen, welche sich in einem bestimmten ressourcenbeschränkten Berechnungsmodell berechnen lassen. Definiert wird eine Komplexitätsklasse durch eine obere Schranke für den Bedarf einer bestimmten Ressource unter Voraussetzung eines Berechnungsmodells. Die am häufigsten betrachteten Ressourcen sind die Anzahl der notwendigen Berechnungsschritte zur Lösung eines Problems (Zeitkomplexität) oder der Bedarf an Speicherplatz (Raum- oder Platzkomplexität). Gemessen wird der Ressourcenbedarf in der Regel durch sein asymptotisches Verhalten an der Obergrenze (dem worst case) in Abhängigkeit von der Länge der Eingabe (Problemgröße). Auch andere Maße des Ressourcenbedarfs sind möglich, etwa der statistische Mittelwert über alle möglichen Eingaben. Dieses Maß ist jedoch formal nur schwer zu analysieren. Da durch eine Komplexitätsklasse nur eine obere Grenze für den Ressourcenbedarf festgelegt ist, wird somit für ein gegebenes Berechnungsmodell eine Hierarchie von Komplexitätsklassen gebildet, wobei weniger mächtige Klassen jeweils vollständig in den jeweils höheren Komplexitätsklassen enthalten sind. Zudem können durch formale Methoden auch über unterschiedliche Berechnungsmodelle oder Ressourcen definierte Klassen zueinander in Bezug gesetzt werden.lassen zueinander in Bezug gesetzt werden.
, В теории алгоритмов классами сложности наз … В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Говоря более узко, классы сложности — это множества предикатов (функций, получающих на вход слово и возвращающих ответ 0 или 1), использующих для вычисления примерно одинаковые количества ресурсов. Для каждого класса существует категория задач, которые являются «самыми сложными» в данном классе. Это означает, что любая задача из класса сводится к такой задаче, и притом сама задача лежит в классе. Такие задачи называют полными задачами (англ. -complete) для данного класса. Наиболее известной полной задачей являются NP-полная задача. Полные задачи — удобный инструмент для доказательства равенства классов. Достаточно для одной такой задачи предоставить алгоритм, решающий её и принадлежащий более маленькому классу, и равенство будет доказано.нькому классу, и равенство будет доказано.
|
| http://dbpedia.org/ontology/thumbnail
|
http://commons.wikimedia.org/wiki/Special:FilePath/Complexity_subsets_pspace.svg?width=300 +
|
| http://dbpedia.org/ontology/wikiPageExternalLink
|
https://web.archive.org/web/20220223014316/https:/theory.cs.princeton.edu/complexity/book.pdf +
, https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.pdf +
, http://fuuu.be/polytech/INFOF408/Introduction-To-The-Theory-Of-Computation-Michael-Sipser.pdf%7Carchive-url=https:/web.archive.org/web/20220207141236/http:/fuuu.be/polytech/INFOF408/Introduction-To-The-Theory-Of-Computation-Michael-Sipser.pdf%7Carchive-date=February +
, https://www.cs.utexas.edu/~ear/cs341/automatabook/AutomataTheoryBook.pdf%7Carchive-url=https:/web.archive.org/web/20220121174820/https:/www.cs.utexas.edu/~ear/cs341/automatabook/AutomataTheoryBook.pdf%7Carchive-date=January +
, https://web.archive.org/web/20210506131638/https:/www.wisdom.weizmann.ac.il/~oded/PSX/prpr-r.pdf +
, https://web.archive.org/web/20210403191124/https:/www.cs.princeton.edu/courses/archive/spring06/cos522/count.pdf +
, https://complexityzoo.uwaterloo.ca/Complexity_Zoo +
, https://cs.uwaterloo.ca/~watrous/QC-notes/QC-notes.22.pdf +
, https://www.cs.princeton.edu/courses/archive/spring03/cs522/book2.ps +
, https://www.cs.princeton.edu/courses/archive/spring06/cos522/count.pdf +
, https://web.archive.org/web/20160416021243/https:/people.cs.umass.edu/~immerman/complexity_theory.html +
, https://www.wisdom.weizmann.ac.il/~oded/PSX/prpr-r.pdf +
, https://web.archive.org/web/20200617175017/https:/eccc.weizmann.ac.il/report/2017/004/download/%7Carchive-date=June +
, https://eccc.weizmann.ac.il/report/2017/004/ +
, https://web.archive.org/web/20190827233504/https:/complexityzoo.uwaterloo.ca/Complexity_Zoo +
, http://theory.cs.princeton.edu/complexity/book.pdf +
, https://courses.cs.washington.edu/courses/cse431/14sp/scribes/lec16.pdf +
, http://www.cs.umass.edu/~immerman/complexity_theory.html +
, https://web.archive.org/web/20220521204917/https:/www.cs.princeton.edu/courses/archive/spring03/cs522/book2.ps +
, https://archive.org/details/computationalcom00aror +
, https://web.archive.org/web/20220618222631/https:/lance.fortnow.com/papers/files/counting.pdf +
, https://web.archive.org/web/20220618022421/https:/cs.uwaterloo.ca/~watrous/QC-notes/QC-notes.22.pdf +
, https://lance.fortnow.com/papers/files/counting.pdf +
, https://web.archive.org/web/20211129075858/https:/courses.cs.washington.edu/courses/cse431/14sp/scribes/lec16.pdf +
, https://web.archive.org/web/20211102102656/https:/www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.pdf%7Carchive-date=November +
|
| http://dbpedia.org/ontology/wikiPageID
|
502426
|
| http://dbpedia.org/ontology/wikiPageLength
|
76250
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1122036777
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Boolean_function +
, http://dbpedia.org/resource/Turing_machine +
, http://dbpedia.org/resource/Interactive_proof_systems +
, http://dbpedia.org/resource/AND_gate +
, http://dbpedia.org/resource/Subset +
, http://dbpedia.org/resource/Upper_bound +
, http://dbpedia.org/resource/Logic_gate +
, http://dbpedia.org/resource/Karp_reduction +
, http://dbpedia.org/resource/NP-hard +
, http://dbpedia.org/resource/Optimization_problem +
, http://dbpedia.org/resource/Randomized_algorithm +
, http://dbpedia.org/resource/Recursively_enumerable_set +
, http://dbpedia.org/resource/Category:Theoretical_computer_science +
, http://dbpedia.org/resource/Binary_number +
, http://dbpedia.org/resource/Set_%28mathematics%29 +
, http://dbpedia.org/resource/University_of_Waterloo +
, http://dbpedia.org/resource/Bounded-error_probabilistic_polynomial +
, http://dbpedia.org/resource/Levin_reduction +
, http://dbpedia.org/resource/Processor_%28computing%29 +
, http://dbpedia.org/resource/List_of_undecidable_problems +
, http://dbpedia.org/resource/Computer +
, http://dbpedia.org/resource/Computational_model +
, http://dbpedia.org/resource/Exponential_function +
, http://dbpedia.org/resource/AC_%28complexity%29 +
, http://dbpedia.org/resource/Polynomial-time_reduction +
, http://dbpedia.org/resource/BPP_%28complexity%29 +
, http://dbpedia.org/resource/Big_O_notation +
, http://dbpedia.org/resource/Quantum_Turing_machine +
, http://dbpedia.org/resource/Sharp-P +
, http://dbpedia.org/resource/Byte +
, http://dbpedia.org/resource/Complete_%28complexity%29 +
, http://dbpedia.org/resource/QMA +
, http://dbpedia.org/resource/File:Turing_machine_2b.svg +
, http://dbpedia.org/resource/Log-space_reduction +
, http://dbpedia.org/resource/Formal_language +
, http://dbpedia.org/resource/NL_%28complexity%29 +
, http://dbpedia.org/resource/EXPSPACE +
, http://dbpedia.org/resource/ZPP_%28complexity%29 +
, http://dbpedia.org/resource/NP-complete +
, http://dbpedia.org/resource/Savitch%27s_theorem +
, http://dbpedia.org/resource/PP_%28complexity%29 +
, http://dbpedia.org/resource/Counting_problem_%28complexity%29 +
, http://dbpedia.org/resource/Blum_axioms +
, http://dbpedia.org/resource/Logical_conjunction +
, http://dbpedia.org/resource/NOT_gate +
, http://dbpedia.org/resource/IP_%28complexity%29 +
, http://dbpedia.org/resource/Michael_Garey +
, http://dbpedia.org/resource/Multitape_Turing_machine +
, http://dbpedia.org/resource/Neil_Immerman +
, http://dbpedia.org/resource/P_versus_NP +
, http://dbpedia.org/resource/Logical_connective +
, http://dbpedia.org/resource/P_%28complexity%29 +
, http://dbpedia.org/resource/Directed_path +
, http://dbpedia.org/resource/Natural_number +
, http://dbpedia.org/resource/Directed_acyclic_graph +
, http://dbpedia.org/resource/Probabilistic_Turing_machine +
, http://dbpedia.org/resource/Space_complexity +
, http://dbpedia.org/resource/Closure_%28mathematics%29 +
, http://dbpedia.org/resource/Computability +
, http://dbpedia.org/resource/File:Difference_between_deterministic_and_Nondeterministic.svg +
, http://dbpedia.org/resource/Category:Measures_of_complexity +
, http://dbpedia.org/resource/Yes-no_question +
, http://dbpedia.org/resource/Church%E2%80%93Turing_thesis +
, http://dbpedia.org/resource/Computability_theory +
, http://dbpedia.org/resource/Princeton_University +
, http://dbpedia.org/resource/Formal_verification +
, http://dbpedia.org/resource/FP_%28complexity%29 +
, http://dbpedia.org/resource/Logarithmic_function +
, http://dbpedia.org/resource/Polynomial_time +
, http://dbpedia.org/resource/Statistical_physics +
, http://dbpedia.org/resource/Open_problem +
, http://dbpedia.org/resource/Primality_test +
, http://dbpedia.org/resource/University_of_Washington +
, http://dbpedia.org/resource/MA_%28complexity%29 +
, http://dbpedia.org/resource/Co-NP +
, http://dbpedia.org/resource/One-sided_error +
, http://dbpedia.org/resource/File:SolidLine.png +
, http://dbpedia.org/resource/File:DottedLine.png +
, http://dbpedia.org/resource/List_of_complexity_classes +
, http://dbpedia.org/resource/Non-uniform_computation +
, http://dbpedia.org/resource/Two-sided_error +
, http://dbpedia.org/resource/Complexity_class +
, http://dbpedia.org/resource/Co-RP +
, http://dbpedia.org/resource/Regular_grammar +
, http://dbpedia.org/resource/Randomized_Logarithmic-space_Polynomial-time +
, http://dbpedia.org/resource/File:Randomized_Complexity_Classes.svg +
, http://dbpedia.org/resource/Decision_problem +
, http://dbpedia.org/resource/Probabilistic_algorithm +
, http://dbpedia.org/resource/Randomized_computation +
, http://dbpedia.org/resource/Prime_number +
, http://dbpedia.org/resource/Advice_%28complexity%29 +
, http://dbpedia.org/resource/Approximation_algorithm +
, http://dbpedia.org/resource/NC_%28complexity%29 +
, http://dbpedia.org/resource/Abstract_machine +
, http://dbpedia.org/resource/P/poly +
, http://dbpedia.org/resource/Category:Computational_complexity_theory +
, http://dbpedia.org/resource/Recursive_language +
, http://dbpedia.org/resource/OR_gate +
, http://dbpedia.org/resource/David_S._Johnson +
, http://dbpedia.org/resource/Cook_reduction +
, http://dbpedia.org/resource/Context-free_grammar +
, http://dbpedia.org/resource/Logarithmic_growth +
, http://dbpedia.org/resource/Network_design +
, http://dbpedia.org/resource/Deterministic +
, http://dbpedia.org/resource/Disjunction +
, http://dbpedia.org/resource/Computational_complexity_theory +
, http://dbpedia.org/resource/Planar_graph +
, http://dbpedia.org/resource/Quantum_information_science +
, http://dbpedia.org/resource/Computational_problem +
, http://dbpedia.org/resource/Time_complexity +
, http://dbpedia.org/resource/Context-sensitive_grammar +
, http://dbpedia.org/resource/Undecidable_problem +
, http://dbpedia.org/resource/String_%28computer_science%29 +
, http://dbpedia.org/resource/Algorithm +
, http://dbpedia.org/resource/Nondeterministic_algorithm +
, http://dbpedia.org/resource/Linguistics +
, http://dbpedia.org/resource/PSPACE +
, http://dbpedia.org/resource/NP_%28complexity%29 +
, http://dbpedia.org/resource/Nondeterministic_Turing_machine +
, http://dbpedia.org/resource/Deterministic_Turing_machine +
, http://dbpedia.org/resource/Space_hierarchy_theorem +
, http://dbpedia.org/resource/File:Interactive_proof_%28complexity%29.svg +
, http://dbpedia.org/resource/FNP_%28complexity%29 +
, http://dbpedia.org/resource/Recursively_enumerable_language +
, http://dbpedia.org/resource/Category:Complexity_classes +
, http://dbpedia.org/resource/Certificate_%28complexity%29 +
, http://dbpedia.org/resource/Interactive_proof_system +
, http://dbpedia.org/resource/Time_hierarchy_theorem +
, http://dbpedia.org/resource/EXPTIME +
, http://dbpedia.org/resource/Mathematical_proof +
, http://dbpedia.org/resource/File:Three_input_Boolean_circuit.jpg +
, http://dbpedia.org/resource/Parallel_algorithm +
, http://dbpedia.org/resource/Polynomial_hierarchy +
, http://dbpedia.org/resource/Alphabet_%28formal_languages%29 +
, http://dbpedia.org/resource/Recursive_set +
, http://dbpedia.org/resource/RL_%28complexity%29 +
, http://dbpedia.org/resource/BQP +
, http://dbpedia.org/resource/Digital_circuit +
, http://dbpedia.org/resource/University_of_Maryland +
, http://dbpedia.org/resource/File:Complexity_subsets_pspace.svg +
, http://dbpedia.org/resource/RP_%28complexity%29 +
, http://dbpedia.org/resource/NEXPTIME +
, http://dbpedia.org/resource/Promise_problem +
, http://dbpedia.org/resource/File:Decision_Problem.svg +
, http://dbpedia.org/resource/Primality_testing +
, http://dbpedia.org/resource/Polynomial +
, http://dbpedia.org/resource/AM_%28complexity%29 +
, http://dbpedia.org/resource/Boolean_circuit +
, http://dbpedia.org/resource/Economics +
, http://dbpedia.org/resource/QIP_%28complexity%29 +
, http://dbpedia.org/resource/Statistical_estimation +
, http://dbpedia.org/resource/Quantum_computer +
, http://dbpedia.org/resource/Function_%28mathematics%29 +
, http://dbpedia.org/resource/Model_of_computation +
, http://dbpedia.org/resource/Bit +
, http://dbpedia.org/resource/BPL_%28complexity%29 +
, http://dbpedia.org/resource/Function_problem +
, http://dbpedia.org/resource/Computational_complexity +
, http://dbpedia.org/resource/Cryptography +
, http://dbpedia.org/resource/Simple_cycle +
, http://dbpedia.org/resource/Negation +
, http://dbpedia.org/resource/Prentice_Hall +
|
| http://dbpedia.org/property/date
|
"2019-08-27"^^xsd:date
|
| http://dbpedia.org/property/url
|
https://web.archive.org/web/20190827233504/https:/complexityzoo.uwaterloo.ca/Complexity_Zoo +
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Cite_web +
, http://dbpedia.org/resource/Template:See_also +
, http://dbpedia.org/resource/Template:Reflist +
, http://dbpedia.org/resource/Template:Snf +
, http://dbpedia.org/resource/Template:Cite_book +
, http://dbpedia.org/resource/Template:Expand_section +
, http://dbpedia.org/resource/Template:Webarchive +
, http://dbpedia.org/resource/Template:Efn +
, http://dbpedia.org/resource/Template:Short_description +
, http://dbpedia.org/resource/Template:Sfn +
, http://dbpedia.org/resource/Template:Notelist +
, http://dbpedia.org/resource/Template:ComplexityClasses +
, http://dbpedia.org/resource/Template:Main +
, http://dbpedia.org/resource/Template:Main_article +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Measures_of_complexity +
, http://dbpedia.org/resource/Category:Computational_complexity_theory +
, http://dbpedia.org/resource/Category:Complexity_classes +
, http://dbpedia.org/resource/Category:Theoretical_computer_science +
|
| http://purl.org/linguistics/gold/hypernym
|
http://dbpedia.org/resource/Set +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Complexity_class?oldid=1122036777&ns=0 +
|
| http://xmlns.com/foaf/0.1/depiction
|
http://commons.wikimedia.org/wiki/Special:FilePath/Interactive_proof_%28complexity%29.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Difference_between_deterministic_and_Nondeterministic.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/DottedLine.png +
, http://commons.wikimedia.org/wiki/Special:FilePath/solidLine.png +
, http://commons.wikimedia.org/wiki/Special:FilePath/dottedLine.png +
, http://commons.wikimedia.org/wiki/Special:FilePath/SolidLine.png +
, http://commons.wikimedia.org/wiki/Special:FilePath/Turing_machine_2b.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Complexity_subsets_pspace.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Randomized_Complexity_Classes.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Three_input_Boolean_circuit.jpg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Decision_Problem.svg +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Complexity_class +
|
| owl:sameAs |
https://global.dbpedia.org/id/54MNp +
, http://www.wikidata.org/entity/Q908207 +
, http://fa.dbpedia.org/resource/%DA%A9%D9%84%D8%A7%D8%B3_%D9%BE%DB%8C%DA%86%DB%8C%D8%AF%DA%AF%DB%8C +
, http://nl.dbpedia.org/resource/Complexiteitsgraad +
, http://zh.dbpedia.org/resource/%E5%A4%8D%E6%9D%82%E6%80%A7%E7%B1%BB +
, http://ro.dbpedia.org/resource/Clas%C4%83_de_complexitate +
, http://ja.dbpedia.org/resource/%E8%A4%87%E9%9B%91%E6%80%A7%E3%82%AF%E3%83%A9%E3%82%B9 +
, http://pl.dbpedia.org/resource/Klasa_z%C5%82o%C5%BCono%C5%9Bci +
, http://it.dbpedia.org/resource/Classe_di_complessit%C3%A0 +
, http://yago-knowledge.org/resource/Complexity_class +
, http://sh.dbpedia.org/resource/Klasa_slo%C5%BEenosti +
, http://nn.dbpedia.org/resource/Kompleksitetsklasse +
, http://rdf.freebase.com/ns/m.02j0nr +
, http://pt.dbpedia.org/resource/Classe_de_complexidade +
, http://ko.dbpedia.org/resource/%EB%B3%B5%EC%9E%A1%EB%8F%84_%EC%A2%85%EB%A5%98 +
, http://sr.dbpedia.org/resource/%D0%9A%D0%BB%D0%B0%D1%81%D0%B0_%D1%81%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%BE%D1%81%D1%82%D0%B8 +
, http://de.dbpedia.org/resource/Komplexit%C3%A4tsklasse +
, http://ca.dbpedia.org/resource/Classe_de_complexitat +
, http://sv.dbpedia.org/resource/Komplexitetsklass +
, http://he.dbpedia.org/resource/%D7%9E%D7%97%D7%9C%D7%A7%D7%AA_%D7%A1%D7%99%D7%91%D7%95%D7%9B%D7%99%D7%95%D7%AA +
, http://hr.dbpedia.org/resource/Klasa_slo%C5%BEenosti +
, http://ru.dbpedia.org/resource/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8 +
, http://no.dbpedia.org/resource/Kompleksitetsklasse +
, http://simple.dbpedia.org/resource/Complexity_class +
, http://ar.dbpedia.org/resource/%D9%82%D8%B3%D9%85_%D8%AA%D8%B9%D9%82%D9%8A%D8%AF +
, http://fr.dbpedia.org/resource/Classe_de_complexit%C3%A9 +
, http://es.dbpedia.org/resource/Clase_de_complejidad +
, http://dbpedia.org/resource/Complexity_class +
|
| rdf:type |
http://dbpedia.org/class/yago/YagoPermanentlyLocatedEntity +
, http://dbpedia.org/class/yago/Cognition100023271 +
, http://dbpedia.org/class/yago/Action100037396 +
, http://dbpedia.org/class/yago/Act100030358 +
, http://dbpedia.org/class/yago/Collection107951464 +
, http://dbpedia.org/class/yago/Group100031264 +
, http://dbpedia.org/class/yago/WikicatMeasuresOfComplexity +
, http://dbpedia.org/class/yago/Decision100162632 +
, http://dbpedia.org/class/yago/Choice100161243 +
, http://dbpedia.org/class/yago/Class107997703 +
, http://dbpedia.org/class/yago/Measure100174412 +
, http://dbpedia.org/class/yago/Maneuver100168237 +
, http://dbpedia.org/class/yago/Concept105835747 +
, http://dbpedia.org/class/yago/WikicatComplexityClasses +
, http://dbpedia.org/class/yago/Idea105833840 +
, http://dbpedia.org/class/yago/Content105809192 +
, http://dbpedia.org/class/yago/Move100165942 +
, http://dbpedia.org/class/yago/Event100029378 +
, http://dbpedia.org/class/yago/Abstraction100002137 +
, http://dbpedia.org/class/yago/PsychologicalFeature100023100 +
, http://dbpedia.org/class/yago/WikicatProgrammingLanguageConcepts +
|
| rdfs:comment |
In der Komplexitätstheorie werden Probleme … In der Komplexitätstheorie werden Probleme oder Algorithmen darauf untersucht, wie aufwendig sie zu berechnen sind bezüglich einer bestimmten Ressource, meist bezüglich des Zeitaufwands oder des (Speicher-)Platzaufwands. Bei Problemen wird dabei stets das „kostengünstigste“ Lösungsverfahren angenommen. Der Aufwand ist im Allgemeinen abhängig von der „Größe“ der Eingabe, wie viele Elemente sie umfasst. Abgeschätzt wird der asymptotische Aufwand, also für sehr viele Eingabeelemente. Dabei zeigt sich, dass die Probleme bzgl. ihres Aufwands Gruppen bilden, deren Aufwand für große Eingabemengen auf ähnliche Weise anwächst; diese Gruppen werden Komplexitätsklassen genannt. Eine Komplexitätsklasse ist eine Menge von Problemen, welche sich in einem bestimmten ressourcenbeschränkten Berechnungsmodeten ressourcenbeschränkten Berechnungsmode
, 複雑性クラス（ふくざつせいクラス、英: Complexity class）は、計算複 … 複雑性クラス（ふくざつせいクラス、英: Complexity class）は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。 抽象機械 M によりO(f(n))の計算資源 R を使って解く事が出来る問題の集合（nは入力長） 例えば、クラスNPは非決定性チューリングマシンで多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEはチューリングマシンでで解く事が出来る決定問題の集合である。ここで、領域とは、実世界ではメモリ空間、チューリングマシンではテープの長さと考えればよい。一部の複雑性クラスは函数問題の集合である（例えば）。 数理論理学では表現の必要に応じて多数の複雑性クラスが定義される（記述計算量）。 ブラムの公理を使うと、完全な計算模型を参照しなくとも複雑性クラスを定義できる。）。 ブラムの公理を使うと、完全な計算模型を参照しなくとも複雑性クラスを定義できる。
, Komplexitetsklass är inom komplexitetsteor … Komplexitetsklass är inom komplexitetsteori en mängd beräkningsproblem som har liknande resursbaserad komplexitet. En typisk komplexitetsklass har en definition likt: mängden av alla problem som kan lösas av en M med O(f(n)) mycket resurser R, där n är storleken på problemet. Till exempel är problem av komplexitetsklass NP de beslutsproblem som en icke-deterministisk turingmaskin kan lösa på polynomiell tid, medan klassen PSPACE är mängden av beslutsproblem som kan lösas av en deterministisk turingmaskin på polynomiellt utrymme. Enklare komplexitetsklasser definieras av tre faktorer:exitetsklasser definieras av tre faktorer:
, Klasa złożoności – zbiór problemów oblicze … Klasa złożoności – zbiór problemów obliczeniowych o podobnej złożoności obliczeniowej. Najbardziej pospolitą definicją klasy złożoności jest: Zbiór problemów, które mogą być rozwiązane na M przy użyciu O(f(n)) zasobu R, gdzie n jest rozmiarem wejścia. Na przykład klasa P to zbiór problemów decyzyjnych, które można rozwiązać na maszynie Turinga w czasie wielomianowym natomiast klasa NP to zbiór problemów decyzyjnych, które można rozwiązać na niedeterministycznej maszynie Turinga w czasie wielomianowym.j maszynie Turinga w czasie wielomianowym.
, Na Teoria da Complexidade Computacional, u … Na Teoria da Complexidade Computacional, uma Classe de Complexidade é um conjunto de problemas relacionados aos recursos computacionais baseados em complexidade. Uma típica classe de complexidade é definida da seguinte forma: O conjunto de problemas que podem ser resolvidos por uma máquina abstrata M usando O(f(n)) de recurso R, onde n é o tamanho da entrada. As mais simples classes de complexidade são definidas pelos seguintes fatores: Muitas classes de complexidade podem ser caracterizadas em termos da matemática lógica, necessária para expressá-las.tica lógica, necessária para expressá-las.
, En informatique théorique, et plus précisé … En informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace. On peut par exemple citer les classes P et NP.eut par exemple citer les classes P et NP.
, في علم التعقيد الحسابي، قسم تعقيد هي مجموع … في علم التعقيد الحسابي، قسم تعقيد هي مجموعة من المسائل المُتعلقة بالاساس فيما بينها بمورد مُعين، اغلب الاقسام لديها التعريف التالي: مجموعة المسائل التي يمكن حلها بواسطة موارد حيث أنَّ n هو طول المُدخل. على سبيل المثال: القسم NP هو مجموعة المسائل التي يمكن حلها بوقت حدودي (أي ) بواسطة آلة تيورنج غير حتمية، مثال آخر هو القسم بيسبايس وهو مجموعة المسائل التي يمكن حلها بواسطة آلة تيورنج حتمية وتستخدم مكان اضافي طوله حدودي (أي انها تسخدم مكان اضافي). الاقسام الأساسية مُعرفة حسب المتغيرات التالية: بعض الاقسام يمكن تشخيصها بواسطة المنطق الرياضي اللازم لتعريفها.صها بواسطة المنطق الرياضي اللازم لتعريفها.
, En teoria de complexitat, una classe de co … En teoria de complexitat, una classe de complexitat és un conjunt de problemes de decisió de complexitat relacionada. Una classe de complexitat típica té una definició de la forma: El conjunt de problemes que se poden resoldre per una màquina abstracta M usant O (f(n)) del recurs R on n és la mida de l'entrada.del recurs R on n és la mida de l'entrada.
, De complexiteitsgraad van een bepaald algoritme is de manier waarop dat algoritme zich gedraagt als de grootte van het op te lossen probleem toeneemt.
, 在計算複雜度理論中，一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下形式： 可以被同一個抽象機器M使用O(f(n))的資源R所解決的問題的集合（n是輸入資料的大小）。 例如NP類別就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類別則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題的集合，例如。 許多複雜度類可為數學邏輯所描述刻劃，請見。 布盧姆複雜度則不需實際抽象機器就可定義複雜度類。
, En teoría de la complejidad computacional, una clase de complejidad es un conjunto de problemas de decisión de complejidad relacionada. Una clase de complejidad tiene una definición de la forma:
, Nella teoria della complessità computazion … Nella teoria della complessità computazionale, una classe di complessità è un insieme di problemi di una certa complessità. Un esempio tipico di definizione di classe di complessità ha la forma: l'insieme di problemi che, se esiste la soluzione, possono essere risolti da una macchina astratta M usando della risorsa R, con dimensione dell'input Molte classi di complessità possono essere caratterizzate in termini della logica matematica necessaria ad esprimerle; vedi . Gli possono essere usati per definire classi di complessità senza riferirsi ad un concreto.omplessità senza riferirsi ad un concreto.
, 복잡도 종류(複雜度 種類)는 계산 복잡도 이론에서 에 따라서 문제를 분류한 것이다. 복잡도 종류의 일반적 정의는 다음과 같은 형태로 되어 있다. 예를 들어, NP는 확률적 튜링 기계가 다항시간에 풀 수 있는 판정 문제의 집합이고 PSPACE는 결정론적 튜링 기계가 다항공간에 풀 수 있는 판정 문제의 집합이다. 함수 문제의 집합인 같은 것도 있다. 구체적인 없이 복잡도 종류를 정의하는 데 사용할 수 있는 도 있다.
, In computational complexity theory, a comp … In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements. For instance, the class P is the set of decision problems solvable by a deterministic Turing machine in polynomial time. There are, however, many complexity classes defined in terms of other types of problems (e.g. counting problems and function problems) and using other modeld function problems) and using other model
, В теории алгоритмов классами сложности наз … В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Говоря более узко, классы сложности — это множества предикатов (функций, получающих на вход слово и возвращающих ответ 0 или 1), использующих для вычисления примерно одинаковые количества ресурсов. Полные задачи — удобный инструмент для доказательства равенства классов. Достаточно для одной такой задачи предоставить алгоритм, решающий её и принадлежащий более маленькому классу, и равенство будет доказано.нькому классу, и равенство будет доказано.
|
| rdfs:label |
複雑性クラス
, Classe di complessità
, 복잡도 종류
, Komplexitetsklass
, 复杂性类
, Clase de complejidad
, Classe de complexitat
, Complexity class
, Komplexitätsklasse
, Klasa złożoności
, قسم تعقيد
, Complexiteitsgraad
, Classe de complexité
, Класс сложности
, Classe de complexidade
|
| rdfs:seeAlso |
http://dbpedia.org/resource/Reduction_%28complexity%29 +
, http://dbpedia.org/resource/List_of_complexity_classes +
|
