| rdfs:comment
| - Cet article présente une liste de classes de complexité en théorie de la complexité. (fr)
- 이 문서는 계산 복잡도 이론에서 다루는 복잡도 종류 목록이다. 다른 계산·복잡도 관련 내용이 궁금하면 을 보자. 복잡도 종류 가운데 원래 종류에 들어 있는 모든 언어의 (complement)으로 이루어진 'co'짝이 있는 종류가 많다. 예를 들어 어떤 언어 L이 NP에 들어 있으면 L의 보완은 co-NP에 들어 있다. (이건 NP의 보완이 co-NP라는 뜻은 아니다. 둘 다에 들어 있는 언어도 있고, 어느 쪽에도 들어 있지 않은 언어도 있다.) 복잡도 종류에서 "가장 어려운 문제"는 같은 종류에 들어 있는 문제라면 모두 그 문제로 환산할 수 있는 문제를 말한다. 환산을 하는 문제 자체도 그 종류에 들어 있거나, 그 종류의 부분집합에 들어 있다. 목록에 없는 문제가 있다면, 짝을 찾아 보면 된다. 이를테면 co-UP가 궁금하면 UP를 본다. (ko)
- 許多複雜度類都有一個前面加上'Co'的同伴，這是包含原來複雜度類裡面所有問題的的一個複雜度類。像是，若一個語言屬於NP，則此語言的補集則屬於Co-NP。（注意這裡不代表NP的補集就等同於Co-NP - 有一些語言同時是NP也是Co-NP，也有語言兩者皆非。） 一個複雜度類裡面"最難的問題"代表這個複雜度類裡面所有的問題都可以歸約為這個問題。此外，歸約過程本身是這個複雜度或者比他更簡單的問題類別裡面。 如果找不到想要看的複雜度類（例如說找不到Co-UP），那可以尋找看看這一個類別的同伴（以剛剛的例子來說：UP）來參考。 (zh)
- Ĉi tio estas listo de en . Multaj el ĉi tiuj klasoj havas asociitan Co-klason, kiu konsistas de la komplementoj de ĉiuj lingvoj de la originala klaso (??? vidu sube (Ĉi ...)). Ekzemple se L estas en NP, tiam la komplemento de L estas en Co-NP. Ĉi tio ne signifas, ke la komplemento de NP estas Co-NP — estas lingvoj kiuj estas sciataj esti ambaŭ, kaj aliaj lingvoj kiuj estas sciataj esti neniun. (eo)
- Dies ist eine Liste von Komplexitätsklassen, die in der Komplexitätstheorie betrachtet werden. Die Klassen verwenden in ihren Definitionen verschiedene Maschinenmodelle. Die wichtigsten Modelle sind Turingmaschinen; diese können deterministisch, nichtdeterministisch oder probabilistisch arbeiten. Als Komplexitätsmaß werden vor allem Zeitkomplexität und Speicherplatzkomplexität betrachtet (in Abhängigkeit von der Problemgröße bzw. Eingabelänge n). Die Abschätzung von konkreter Laufzeit oder Speicherplatzverbrauch wird durch die Landau-Notation ausgedrückt. (de)
- This is a list of complexity classes in computational complexity theory. For other computational and complexity subjects, see list of computability and complexity topics. Many of these classes have a 'co' partner which consists of the complements of all languages in the original class. For example, if a language L is in NP then the complement of L is in co-NP. (This does not mean that the complement of NP is co-NP—there are languages which are known to be in both, and other languages which are known to be in neither.) (en)
- Questa pagina contiene la lista delle classi di complessità, insiemi concernenti la teoria della complessità computazionale. Nell'articolo computazione compare una mappa delle relazioni di inclusione dimostrabili per le classi di complessità.Molte delle classi sottoindicate hanno una classe associata in modo involutorio che chiamiamo "co-duale" costituita dai complementi di tutti i linguaggi della classe originale. Ad esempio, se il linguaggio appartiene a NP, il complementare di sta in co-NP (questo non è il complementare dell'insieme di linguaggi NP, in quanto vi sono linguaggi in entrambe queste classi e linguaggi che non appartengono a nessuno dei due). Per una classe co-duale non presente in genere è utile esaminare la associata: ad esempio da UP si possono ricavare indicazioni per (it)
- Essa é uma lista de classes de complexidade da teoria da complexidade computacional. Para outros assuntos sobre computabilidade e complexidade, veja . Muitas dessas classes tem uma outra classe com prefixo 'co' que corresponde ao complemento de todas as linguagens da classe original. Por exemplo, se uma linguagem L está em NP então o complemento de L está em co-NP (isso não significa que o complemento de NP é co-NP - exitem linguagens que são conhecidas por estarem nas duas classes, e outras que são conhecidas por não estarem em nenhuma delas). (pt)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[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)