| dbo:abstract
|
- 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. Für jede Klasse ist – falls möglich – die Definition in der DTIME-, DSPACE-, NTIME- oder NSPACE-Notation, sowie eine kurze natürlichsprachige Erklärung angegeben. (de)
- Ĉ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. La plej malfacilaj problemoj de klaso estas problemoj, kiuj apartenas la klaso kaj ĉiu alia problemo de tiu klaso povas reduktiĝi al ili. Plue, la malpligrandiĝo estas ankaŭ problemo de la donita klaso, aŭ ĝia subaro. (eo)
- Cet article présente une liste de classes de complexité en théorie de la complexité. (fr)
- 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.) "The hardest problems" of a class refer to problems which belong to the class such that every other problem of that class can be reduced to it. Furthermore, the reduction is also a problem of the given class, or its subset. (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 co-UP. (it)
- 이 문서는 계산 복잡도 이론에서 다루는 복잡도 종류 목록이다. 다른 계산·복잡도 관련 내용이 궁금하면 을 보자. 복잡도 종류 가운데 원래 종류에 들어 있는 모든 언어의 (complement)으로 이루어진 'co'짝이 있는 종류가 많다. 예를 들어 어떤 언어 L이 NP에 들어 있으면 L의 보완은 co-NP에 들어 있다. (이건 NP의 보완이 co-NP라는 뜻은 아니다. 둘 다에 들어 있는 언어도 있고, 어느 쪽에도 들어 있지 않은 언어도 있다.) 복잡도 종류에서 "가장 어려운 문제"는 같은 종류에 들어 있는 문제라면 모두 그 문제로 환산할 수 있는 문제를 말한다. 환산을 하는 문제 자체도 그 종류에 들어 있거나, 그 종류의 부분집합에 들어 있다. 목록에 없는 문제가 있다면, 짝을 찾아 보면 된다. 이를테면 co-UP가 궁금하면 UP를 본다. (ko)
- 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). "Os problemas mais difíceis" de uma classe referem-se aos problemas que pertencem a classe e todos os outros problemas dessa classe podem ser reduzidos a ele, além disso, a redução é também um problema da classe determinada ou de seu subconjunto.
* #P Contagem de soluções para um problema NP.
* #P-complete Os problemas mais difíceis em #P.
* 2-EXPTIME Solúveis em tempo duplamente exponencial.
* AC0 Uma classe de complexidade de circuito de profundidade limitada.
* ACC0 Uma classe de complexidade de circuito de profundidade limitada e contagem de portas.
* AC Uma classe de complexidade de circuito.
* AH A hierarquia aritmética.
* AP A classe de problemas que uma máquina de Turing alternada pode resolver em tempo polinomial.
* APX Problemas de otimização que possuem algoritmos de aproximação com um rácio de aproximação constante.
* AM Solúveis em tempo polinomial por um protocolo Arthut-Merlin.
* BPP Solúveis em tempo polinomial por algoritmos randomizados (a resposta provavelmente é correta).
* BQP Solúveis em tempo polinomial por um computador quântico (a resposta provavelmente é correta).
* co-NP Respostas "Não" verificáveis em tempo polinomial por uma máquina de Turing não determinística.
* co-NP-complete Os problemas mais difíceis em co-NP.
* DSPACE(f(n)) Solúveis por uma máquina de Turing determinística com espaço O(f(n)).
* DTIME(f(n)) Solúveis por uma máquina de Turing determinística em tempo O(f(n)).
* E Solúveis em tempo exponencial com expoente linear.
* ELEMENTARY A união das classes na hierarquia exponencial.
* ESPACE Solúvel com espaço exponencial com expoente linear.
* EXP O mesmo que EXPTIME.
* EXPSPACE Solúvel com espaço exponencial.
* EXPTIME Solúvel em tmepo exponencial.
* FNP O análogo à NP para problemas de função.
* FP O análogo à P para problemas de função.
* FPNP O análogo à PNP para problemas de função; A origem do problema do caixeiro viajante.
* FPT Parâmetro fixo tratável.
* GapL Redutível em espaço logarítmico para computar o determinante inteiro de uma matriz.
* IP Solúvel em tempo polinomial por um sistema de prova interativo.
* L Solúvel com um espaço logarítmico (pequeno).
* LOGCFL Redutível em espaço logarítmico para uma linguagem livre do contexto.
* MA Solúvel em tempo polinomial por um protocolo Merlin-Arthur.
* NC Solúvel eficientemente (em tempo polylog) em computação paralela.
* NE Solúvel por uma máquina de Turing não determinística em tempo exponencial com expoente linear.
* NESPACE Solúvel por uma máquina de Turing não determinística com espaço exponencial com expoente linear.
* NEXP O mesmo que NEXPTIME.
* NEXPSPACE Solúvel por uma máquina de Turing não determinística com espaço exponencial.
* NEXPTIME Solúvel por uma máquina de Turing não determinística em tempo exponencial.
* NL Respostas "Sim" verificáveis com espaço logarítmico.
* NONELEMENTARY Complemento de ELEMENTARY.
* NP Respostas "Sim" verificáveis em tempo polinomial.
* NP-complete Os problemas mais difíceis ou mais caros em NP.
* NP-easy O análogo à PNP para problemas de função; outro nome para FPNP.
* NP-equivalent Os problemas mais difíceis em FPNP.
* NP-hard Pelo menos tão difícil quanto todos os problemas em NP, mas não conhecido por ser da mesma classe de complexidade.
* NSPACE(f(n)) Solúvel por uma máquina de Turing não determinística com espaço O(f(n)).
* NTIME(f(n)) Solúvel por uma máquina de Turing não determinística em temo O(f(n)).
* P Solúveis em tempo polinomial.
* P-complete Os problemas mais difíceis em P para resolver em computadores paralelos.
* P/poly Solúvel em tempo polinomial dado uma "dica" dependendo apenas do tamanho da entrada.
* PCP Prova probabilisticamente verificável.
* PH A união das classes na hierarquia polinomial.
* PNP Solúvel em tempo polinomial com um oráculo para um problema em NP; também conhecido como Δ2P.
* PP Probabilisticamente polinomial (resposta está correta com probabilidade ligeiramente superior a 1/2).
* PR Solúvel por recursividade desenvolvendo funções aritméticas.
* PSPACE Solúvel com espaço polinomial.
* PSPACE-complete Os problemas mais difíceis em PSPACE.
* R Solúvel me uma quantidade finita de tempo.
* RE Problemas a que podemos responder "Sim" em uma quantidade finita de tempo, mas um "Não" como resposta pode nunca vir.
* RL Solúvel com espaço logarítmico por algoritmos randomizados (respostas "Não" são provavelmente corretas, respostas "Sim" certamente são corretas).
* RP Solúvel em tempo logarítmico por algoritmos randomizados (respostas "Não" são provavelmente corretas, respostas "Sim" certamente são corretas).
* SL Problemas log-space redutíveis a determinar se existe um caminho entre dados vértices em um grafo não direcionado. Em outubro de 2004 descobriu-se que esta classe é, de fato, igual a L.
* S2P Jogos de uma rodada com movimentos simultâneos arbitrados deterministicamente em tempo polinomial.
* TFNP Total de problemas de função que podem ser resolvidos em tempo polinomial não determinístico. Um problema nesta classe tem a propriedade de que cada entrada tem uma saída cuja validade pode ser verificada de forma eficiente, e o desafio computacional é encontrar uma saída válida.
* UP Funções inequívocas não determinísticas de tempo polinomial.
* ZPL Solúvel por algoritmos randomizados (a resposta é sempre correta, o uso médio do espaço é logarítmico).
* ZPP Solúvel por algoritmos randomizados (a resposta é sempre correta, o tempo médio de execução é polinomial). (pt)
- 許多複雜度類都有一個前面加上'Co'的同伴，這是包含原來複雜度類裡面所有問題的的一個複雜度類。像是，若一個語言屬於NP，則此語言的補集則屬於Co-NP。（注意這裡不代表NP的補集就等同於Co-NP - 有一些語言同時是NP也是Co-NP，也有語言兩者皆非。） 一個複雜度類裡面"最難的問題"代表這個複雜度類裡面所有的問題都可以歸約為這個問題。此外，歸約過程本身是這個複雜度或者比他更簡單的問題類別裡面。 如果找不到想要看的複雜度類（例如說找不到Co-UP），那可以尋找看看這一個類別的同伴（以剛剛的例子來說：UP）來參考。 (zh)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 8053 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| 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)
|
| rdfs:label
|
- Liste von Komplexitätsklassen (de)
- Listo de klasoj de komplikeco (eo)
- Lista delle classi di complessità (it)
- Liste de classes de complexité (fr)
- List of complexity classes (en)
- 복잡도 종류 목록 (ko)
- Lista de classes de complexidade (pt)
- 複雜度類列表 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is rdfs:seeAlso
of | |
| is foaf:primaryTopic
of | |
