| dbo:abstract
|
- In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. Equivalently, if we define decision problems as sets of finite strings, then the complement of this set over some fixed domain is its complement problem. For example, one important problem is whether a number is a prime number. Its complement is to determine whether a number is a composite number (a number which is not prime). Here the domain of the complement is the set of all integers exceeding one. There is a Turing reduction from every problem to its complement problem. The complement operation is an involution, meaning it "undoes itself", or the complement of the complement is the original problem. One can generalize this to the complement of a complexity class, called the complement class, which is the set of complements of every problem in the class. If a class is called C, its complement is conventionally labelled co-C. Notice that this is not the complement of the complexity class itself as a set of problems, which would contain a great deal more problems. A class is said to be closed under complement if the complement of any problem in the class is still in the class. Because there are Turing reductions from every problem to its complement, any class which is closed under Turing reductions is closed under complement. Any class which is closed under complement is equal to its complement class. However, under many-one reductions, many important classes, especially NP, are believed to be distinct from their complement classes (although this has not been proven). The closure of any complexity class under Turing reductions is a superset of that class which is closed under complement. The closure under complement is the smallest such class. If a class is intersected with its complement, we obtain a (possibly empty) subset which is closed under complement. Every deterministic complexity class (DSPACE(f(n)), DTIME(f(n)) for all f(n)) is closed under complement, because one can simply add a last step to the algorithm which reverses the answer. This doesn't work for nondeterministic complexity classes, because if there exist both computation paths which accept and paths which reject, and all the paths reverse their answer, there will still be paths which accept and paths which reject — consequently, the machine accepts in both cases. Similarly, probabilistic classes such as BPP, ZPP, BQP or PP which are defined symmetrically with regards to their yes and no instances are closed under complement. In contrast, classes such as RP and co-RP define their probabilities with one-sided error, and so are not (currently known to be) closed under complement. Some of the most surprising complexity results shown to date showed that the complexity classes NL and SL are in fact closed under complement, whereas before it was widely believed they were not (see Immerman–Szelepcsényi theorem). The latter has become less surprising now that we know SL equals L, which is a deterministic class. Every class which is low for itself is closed under complement. (en)
- En théorie de la complexité (un domaine de l'informatique théorique), on parle du complémentaire d'une classe C, noté co-C ou coC, pour désigner l'ensemble des langages complémentaires des langages de la classe. Cet opérateur amène à considérer de nouvelles classes comme co-NP, le complémentaire de NP. (fr)
- En teoría de la complejidad computacional, el complemento de un problema de decisión es el problema de decisión que resulta de invertir las respuestas sí y no. De manera equivalente, si se definen los problemas de decisión como conjuntos de cadenas finitas, entonces el complemento de este conjunto sobre algún dominio fijo es su problema de complemento. (es)
- Nella teoria della complessità computazionale, il complemento di un problema decisionale è il problema risultante dall'inversione delle risposte sì e no. In maniera equivalente, se definiamo un problema decisionale come un insieme di stringhe finite, allora il complemento di questo insieme su un certo dominio è il suo problema complementare. Per esempio, un importante problema è stabilire se un numero sia o no primo. Il suo complemento è di determinare se un numero è composto (ovvero, se non è primo). In questo caso, il dominio del complemento è l'insieme di tutti gli interi tranne uno. Esiste una Turing-riduzione da ogni problema al suo complemento. L'operazione complementare è l'involuzione, ovvero il complemento del problema originale. Le precedenti nozioni possono essere estese al livello delle classi di complessità, ottenendo così il concetto di classe complemento (o classe complementare), che è l'insieme dei complementi di tutti i problemi della classe data. Presa una classe C qualsiasi, il suo complemento viene convenzionalmente indicato con co-C. Da notare che una classe complemento non è il complemento della classe in quanto insieme di problemi, il quale conterrebbe un numero di problemi assai maggiore. Una classe di complessità è detta essere chiusa rispetto al complemento se il complemento di ciascun problema della classe appartiene alla classe stessa. Dato che esiste una Turing-riduzione da ogni problema al suo complemento, ogni classe che è chiusa rispetto alle Turing-riduzioni è chiusa rispetto al complemento. Ogni classe chiusa rispetto al complemento è uguale alla sua classe complementare. Per quanto riguarda le classi chiuse rispetto alle cosiddette riduzioni "many-one", invece, si crede che molte classi importanti (tra cui NP, in particolare) siano distinte dal proprio complemento (nello specifico, co-NP), anche se non è stato provato. Ogni classe di complessità deterministica (DSPACE(f(n)), DTIME(f(n)), per ogni f(n)) è chiusa rispetto al complemento, perché si può semplicemente aggiungere un ultimo passo all'algoritmo che inverte la risposta. Questo espediente non funziona per le classi di complessità non deterministiche: dati, infatti, due percorsi computazionali, uno accettante ed uno respingente, pur facendo in modo che essi neghino il proprio risultato, continueranno ad esistere due percorsi uno dei quali sarà accettante; quindi la macchina, in maniera non deterministica, troverà ancora il modo di accettare ed il problema continuerà ad avere esito positivo (e, di conseguenza, non rappresenterà il complemento del problema di partenza). (it)
- Na teoria da complexidade computacional, o complemento de um problema de decisão é o problema de decisão resultante do reverso das respostas sim e não.Igualmente, se definimos problemas de decisão como um conjunto de cadeias finitas, então o complemento deste conjunto sobre um domínio fixo é seu problema-complemento. Por exemplo, um problema importante é se um número é primo. Seu complemento é determinar se o número é um número composto (número que não é primo). Neste caso, o domínio do complemento é o conjunto de inteiros maiores do que um. Existe uma Turing redução de todo problema para o seu complemento. A operação de complemento é uma Involução, que significa "se desfaz", ou o complemento do seu complemento é o problema original. Isto pode se generalizar para o complemento de uma classe de complexidade, chamadas de classe de complemento, que é o conjunto dos complementos de cada problema na classe. Se uma classe é chamada C, seu complemento por convenção é chamado de co-C. Observe que isso não é o complemento da classes de complexidade propriamente dita como um conjunto de problemas, que conteria muito mais problemas. Uma classe é dita fechada sob complemento se o complemento de qualquer problema na classe ainda pertencer à classe. Em razão do fato de que existem Turing-reduções de qualquer problema para o seu complemento, qualquer classe que é fechada sob Turing-redução é fechada sob complemento. Qualquer classe que é fechada sob complemento é equivalente ao seu complemento. No entanto, sob redução por mapeamento, muitas classes importantes, especialmente NP, acredita-se que são distintas de seu complemento (embora não tenha sido provado). O fechamento de qualquer classe de complexidade sob uma Turing-redução é um superconjunto das classes que são fechadas sob complemento. O fecho sob complemento é a menor dessas classes. Se uma classe for operada pela interseção com o seu complemento, obtém-se um subconjunto (possivelmente vazio) que é fechado sob complemento. Toda classe de complexidade determinística (DSAPCE(f(n)), DTIME(f(n)) para todo f(n)) é fechado sob complemento, pois pode ser adicionado um último passo ao algoritmo no qual se inverte a resposta. Isto não funciona para classes de complexidade não -determinísticas, pois se existe tanto caminhos que aceitam quanto caminhos que rejeitam, e todos os caminhos inverterem suas respostas, vão existir caminhos que aceitam e caminhos que rejeitam - consequentemente, a máquina aceita em ambos os casos. Alguns dos mais surpreendentes resultados mostrados até agora mostraram que as classes de complexidade NL e SL são de fato fechadas sob seu complemento, enquanto que antes acreditava-se que elas não eram (veja Teorema de Immerman - Szelepcsényi). Este último tornou -se menos surpreendente quando sabemos que SL é igual a L, que é uma classe determinística. Toda classe que é low é fechada sob complemento. (pt)
- Dopełnienie – problem decyzyjny powstający po zamianie miejscami odpowiedzi tak i nie. Równoważnie, jeśli zdefiniujemy proces decyzyjny jako zbiór skończonych napisów, dopełnienie zbioru tych napisów nad ich alfabetem jest dopełnieniem problemu. Przykładowo, jeśli rozważymy problem decyzyjny określania czy dana liczba jest liczbą pierwszą, to dopełnieniem tego problemu będzie określanie czy dana liczba jest liczbą złożoną. Uogólniając tę operację na klasy złożoności obliczeniowej, możemy wprowadzić klasy będące dopełnieniem problemów w danej klasie. Jeśli pierwotna klasa nazywana jest C, jej klasa dopełniająca jest nazywana Co-C. Należy pamiętać, że nie jest ona dopełnieniem tej klasy jako zbioru problemów – dopełnienie takie zawiera zwykle znacznie więcej problemów. Klasa złożoności może być zamknięta na dopełnienie, jeśli dopełnienie każdego problemu w tej klasie należy do tej klasy. Ponieważ istnienie redukcja Turinga z każdego problemu do jego dopełnienia, każda klasa zamknięta na redukcje Turinga jest zamknięta na dopełnienie. Każda klasa zamknięta na dopełnienie jest równa swojej klasie dopełniającej. W szczególności wszystkie klasy deterministyczne DSPACE(f(n)) i DTIME(f(n)), dla wszystkich f(n), są zamknięte na dopełnienie, ponieważ można zawsze dodać ostatni krok do maszyny Turinga, który odwraca odpowiedź. Ta metoda nie działa dla niedeterministycznych klas, ponieważ, jeśli istnieją ścieżki obliczeń zarówno akceptujące jak i nieakceptujące, odwrócenie odpowiedzi na końcu każdego obliczenia nic nie zmienia – w obu przypadkach maszyna odpowiada akceptująco. Wiele istotnych klas jest uważanych za różne od swoich dopełnień. W szczególności NP uważa się za różne od Co-NP, choć nie zostało to udowodnione. Jednym z najbardziej zaskakujących rezultatów w teorii złożoności jest pokazujące, że wszystkie niedeterministyczne klasy pamięciowe NSPACE są zamknięte na dopełnienie. (pl)
|
| rdfs:comment
|
- En théorie de la complexité (un domaine de l'informatique théorique), on parle du complémentaire d'une classe C, noté co-C ou coC, pour désigner l'ensemble des langages complémentaires des langages de la classe. Cet opérateur amène à considérer de nouvelles classes comme co-NP, le complémentaire de NP. (fr)
- En teoría de la complejidad computacional, el complemento de un problema de decisión es el problema de decisión que resulta de invertir las respuestas sí y no. De manera equivalente, si se definen los problemas de decisión como conjuntos de cadenas finitas, entonces el complemento de este conjunto sobre algún dominio fijo es su problema de complemento. (es)
- In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. Equivalently, if we define decision problems as sets of finite strings, then the complement of this set over some fixed domain is its complement problem. For example, one important problem is whether a number is a prime number. Its complement is to determine whether a number is a composite number (a number which is not prime). Here the domain of the complement is the set of all integers exceeding one. (en)
- Nella teoria della complessità computazionale, il complemento di un problema decisionale è il problema risultante dall'inversione delle risposte sì e no. In maniera equivalente, se definiamo un problema decisionale come un insieme di stringhe finite, allora il complemento di questo insieme su un certo dominio è il suo problema complementare. Per esempio, un importante problema è stabilire se un numero sia o no primo. Il suo complemento è di determinare se un numero è composto (ovvero, se non è primo). In questo caso, il dominio del complemento è l'insieme di tutti gli interi tranne uno. (it)
- Dopełnienie – problem decyzyjny powstający po zamianie miejscami odpowiedzi tak i nie. Równoważnie, jeśli zdefiniujemy proces decyzyjny jako zbiór skończonych napisów, dopełnienie zbioru tych napisów nad ich alfabetem jest dopełnieniem problemu. Przykładowo, jeśli rozważymy problem decyzyjny określania czy dana liczba jest liczbą pierwszą, to dopełnieniem tego problemu będzie określanie czy dana liczba jest liczbą złożoną. Wiele istotnych klas jest uważanych za różne od swoich dopełnień. W szczególności NP uważa się za różne od Co-NP, choć nie zostało to udowodnione. (pl)
- Na teoria da complexidade computacional, o complemento de um problema de decisão é o problema de decisão resultante do reverso das respostas sim e não.Igualmente, se definimos problemas de decisão como um conjunto de cadeias finitas, então o complemento deste conjunto sobre um domínio fixo é seu problema-complemento. Por exemplo, um problema importante é se um número é primo. Seu complemento é determinar se o número é um número composto (número que não é primo). Neste caso, o domínio do complemento é o conjunto de inteiros maiores do que um. Toda classe que é low é fechada sob complemento. (pt)
|
