| rdfs:comment
| - 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. (fr)
- 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: (es)
- 복잡도 종류(複雜度 種類)는 계산 복잡도 이론에서 에 따라서 문제를 분류한 것이다. 복잡도 종류의 일반적 정의는 다음과 같은 형태로 되어 있다. 예를 들어, NP는 확률적 튜링 기계가 다항시간에 풀 수 있는 판정 문제의 집합이고 PSPACE는 결정론적 튜링 기계가 다항공간에 풀 수 있는 판정 문제의 집합이다. 함수 문제의 집합인 같은 것도 있다. 구체적인 없이 복잡도 종류를 정의하는 데 사용할 수 있는 도 있다. (ko)
- 複雑性クラス（ふくざつせいクラス、英: Complexity class）は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。 抽象機械 M によりO(f(n))の計算資源 R を使って解く事が出来る問題の集合（nは入力長） 例えば、クラスNPは非決定性チューリングマシンで多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEはチューリングマシンでで解く事が出来る決定問題の集合である。ここで、領域とは、実世界ではメモリ空間、チューリングマシンではテープの長さと考えればよい。一部の複雑性クラスは函数問題の集合である（例えば）。 数理論理学では表現の必要に応じて多数の複雑性クラスが定義される（記述計算量）。 ブラムの公理を使うと、完全な計算模型を参照しなくとも複雑性クラスを定義できる。 (ja)
- De complexiteitsgraad van een bepaald algoritme is de manier waarop dat algoritme zich gedraagt als de grootte van het op te lossen probleem toeneemt. (nl)
- 在計算複雜度理論中，一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下形式： 可以被同一個抽象機器M使用O(f(n))的資源R所解決的問題的集合（n是輸入資料的大小）。 例如NP類別就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類別則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題的集合，例如。 許多複雜度類可為數學邏輯所描述刻劃，請見。 布盧姆複雜度則不需實際抽象機器就可定義複雜度類。 (zh)
- في علم التعقيد الحسابي، قسم تعقيد هي مجموعة من المسائل المُتعلقة بالاساس فيما بينها بمورد مُعين، اغلب الاقسام لديها التعريف التالي: مجموعة المسائل التي يمكن حلها بواسطة موارد حيث أنَّ n هو طول المُدخل. على سبيل المثال: القسم NP هو مجموعة المسائل التي يمكن حلها بوقت حدودي (أي ) بواسطة آلة تيورنج غير حتمية، مثال آخر هو القسم بيسبايس وهو مجموعة المسائل التي يمكن حلها بواسطة آلة تيورنج حتمية وتستخدم مكان اضافي طوله حدودي (أي انها تسخدم مكان اضافي). الاقسام الأساسية مُعرفة حسب المتغيرات التالية: بعض الاقسام يمكن تشخيصها بواسطة المنطق الرياضي اللازم لتعريفها. (ar)
- 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. (ca)
- 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 model (en)
- 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 Berechnungsmode (de)
- 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. (it)
- 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. (pl)
- 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. (pt)
- 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: (sv)
- В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Говоря более узко, классы сложности — это множества предикатов (функций, получающих на вход слово и возвращающих ответ 0 или 1), использующих для вычисления примерно одинаковые количества ресурсов. Полные задачи — удобный инструмент для доказательства равенства классов. Достаточно для одной такой задачи предоставить алгоритм, решающий её и принадлежащий более маленькому классу, и равенство будет доказано. (ru)
|
.svg)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
![[RDF Data]](/fct/images/sw-rdf-blue.png)