In computational complexity theory, the complexity class NP-equivalent is the set of function problems that are both NP-easy and NP-hard. NP-equivalent is the analogue of NP-complete for function problems. To show that FIND-SUBSET-SUM is NP-equivalent, we must show that it is both NP-hard and NP-easy. Clearly it is NP-hard. If we had a black box that solved FIND-SUBSET-SUM in unit time, then it would be easy to solve SUBSET-SUM. Simply ask the black box to find the subset that sums to zero, then check whether it returned a nonempty set.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - NP-Äquivalenz (de)
- NP-equivalente (es)
- NP-equivalent (en)
- NP-equivalente (pt)
|
| rdfs:comment
| - NP-Äquivalenz ist ein Begriff aus der Komplexitätstheorie innerhalb der Informatik. Es liefert eine prinzipielle Aussage darüber, ob Suchprobleme mit wachsender Anzahl der zu durchsuchenden Pfade oder Objekte noch praktisch lösbar sind, oder ob der benötigte Zeit- oder Speicheraufwand rasch in makrokosmische Dimensionen wächst. Formal ist ein Suchproblem NP-äquivalent, wenn es NP-leicht und NP-schwer ist. Dies ist genau dann der Fall, wenn das zugehörige Entscheidungsproblem NP-vollständig ist. Ein NP-äquivalentes Problem ist genau dann in polynomieller Zeit lösbar, wenn P=NP ist. (de)
- En teoría de la complejidad computacional, la clase de complejidad NP-equivalente es el conjunto de problemas de la función que son NP-fácil y NP-duro. NP-equivalente es el análogo de NP-completo para problemas de la función. Para demostrar que BUSQUEDA-SUBCONJUNTO-SUMA es NP-equivalente,se debe demostrar que es a la vez NP-duro y NP-fácil. función BUSQUEDA-SUBCONJUNTO-SUMA(conjunto S) si no(SUBCONJUNTO-SUMA(S)) retornar {} para cada x en S si SUBCONJUNTO-SUMA(S - {x}) S := S - {x} retornar S (es)
- In computational complexity theory, the complexity class NP-equivalent is the set of function problems that are both NP-easy and NP-hard. NP-equivalent is the analogue of NP-complete for function problems. To show that FIND-SUBSET-SUM is NP-equivalent, we must show that it is both NP-hard and NP-easy. Clearly it is NP-hard. If we had a black box that solved FIND-SUBSET-SUM in unit time, then it would be easy to solve SUBSET-SUM. Simply ask the black box to find the subset that sums to zero, then check whether it returned a nonempty set. (en)
- Em complexidade computacional, a classe de complexidade NP-equivalente é a classe de problemas que são tanto NP-fácil quanto NP-difícil. . Por exemplo, o problema ACHAR-SUBCONJUNTO-SOMA está em NP-equivalente. Dado um conjunto de números inteiros, ACHAR-SUBCONJUNTO-SOMA é o problema que consiste em encontrar algum subconjunto dos inteiros que somam zero (caso não exista tão subconjunto, o conjunto vazio deve ser retornado). Esse problema de otimização é parecido com o problema de decisão SUBCONJUNTO-SOMA. Dado uma lista de inteiros, SUBCONJUNTO-SOMA é o problema que consiste em decidir se existe algum subconjunto cujos integrantes somem zero (ou seja, esse problema retorna apenas uma de duas possíveis respostas: sim ou não. O problema ACHAR-SUBCONJUNTO-SOMA retorna um conjunto). SUBSCONJUN (pt)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - NP-Äquivalenz ist ein Begriff aus der Komplexitätstheorie innerhalb der Informatik. Es liefert eine prinzipielle Aussage darüber, ob Suchprobleme mit wachsender Anzahl der zu durchsuchenden Pfade oder Objekte noch praktisch lösbar sind, oder ob der benötigte Zeit- oder Speicheraufwand rasch in makrokosmische Dimensionen wächst. Formal ist ein Suchproblem NP-äquivalent, wenn es NP-leicht und NP-schwer ist. Dies ist genau dann der Fall, wenn das zugehörige Entscheidungsproblem NP-vollständig ist. Ein NP-äquivalentes Problem ist genau dann in polynomieller Zeit lösbar, wenn P=NP ist. (de)
- En teoría de la complejidad computacional, la clase de complejidad NP-equivalente es el conjunto de problemas de la función que son NP-fácil y NP-duro. NP-equivalente es el análogo de NP-completo para problemas de la función. Por ejemplo, el problema BUSQUEDA-SUBCONJUNTO-SUMA es NP-equivalent. Dado un conjunto de números enteros, BUSQUEDA-SUBCONJUNTO-SUMA es el problema de encontrar algún subconjunto no vacío de enteros cuya suma sea cero (o devolver el conjunto vacío si no existe tal subconjunto). Este problema de optimización es similar al problema de decisión SUBCONJUNTO-SUMA. Dado un conjunto de números enteros, SUBCONJUNTO-SUMA es el problema de saber si existe algún subconjunto cuya suma sea exactamente cero. SUBCONJUNTO-SUMA es NP-Completo. Para demostrar que BUSQUEDA-SUBCONJUNTO-SUMA es NP-equivalente,se debe demostrar que es a la vez NP-duro y NP-fácil. Está claro que es NP-duro. Si tuviéramos un caja negra que resuelve BUSQUEDA-SUBCONJUNTO-SUMA en una unidad de tiempo, entonces sería fácil de resolver SUBCONJUNTO-SUMA. Simplemente se pregunta a la caja negra para que encuentre el subconjunto que sume cero, a continuación, se comprueba si se ha devuelto un conjunto no vacío. También es NP-fácil. Si tuviéramos un caja negra que resuelve SUBCONJUNTO-SUMA en una unidad de tiempo, entonces podríamos utilizarlo para resolver BUSQUEDA-SUBCONJUNTO-SUMA. Si devuelve falso, devolvemos inmediatamente el conjunto vacío. De lo contrario, visitamos cada elemento en orden y lo eliminamos con tal de que SUBCONJUNTO-SUMA adquiera regreso verdadero después de que lo removamos. Una vez que hemos visitado todos los elementos, ya no podremos ser capaces de eliminar cualquier elemento sin cambiar la respuesta de verdadero a falso; en este punto el subconjunto restante de los elementos originales debe sumar cero. Esto nos obliga a señalar que las eliminaciones posteriores de elementos no alteran el hecho de que la eliminación de un elemento anterior cambió la respuesta de verdadero a falso. En pseudocódigo: función BUSQUEDA-SUBCONJUNTO-SUMA(conjunto S) si no(SUBCONJUNTO-SUMA(S)) retornar {} para cada x en S si SUBCONJUNTO-SUMA(S - {x}) S := S - {x} retornar S Otro de los problemas NP-equivalente conocido es el Problema del viajante. (es)
- In computational complexity theory, the complexity class NP-equivalent is the set of function problems that are both NP-easy and NP-hard. NP-equivalent is the analogue of NP-complete for function problems. For example, the problem FIND-SUBSET-SUM is in NP-equivalent. Given a set of integers, FIND-SUBSET-SUM is the problem of finding some nonempty subset of the integers that adds up to zero (or returning the empty set if there is no such subset). This optimization problem is similar to the decision problem SUBSET-SUM. Given a set of integers, SUBSET-SUM is the problem of finding whether there exists a subset summing to zero. SUBSET-SUM is NP-complete. To show that FIND-SUBSET-SUM is NP-equivalent, we must show that it is both NP-hard and NP-easy. Clearly it is NP-hard. If we had a black box that solved FIND-SUBSET-SUM in unit time, then it would be easy to solve SUBSET-SUM. Simply ask the black box to find the subset that sums to zero, then check whether it returned a nonempty set. It is also NP-easy. If we had a black box that solved SUBSET-SUM in unit time, then we could use it to solve FIND-SUBSET-SUM. If it returns false, we immediately return the empty set. Otherwise, we visit each element in order and remove it provided that SUBSET-SUM would still return true after we remove it. Once we've visited every element, we will no longer be able to remove any element without changing the answer from true to false; at this point the remaining subset of the original elements must sum to zero. This requires us to note that later removals of elements do not alter the fact that removal of an earlier element changed the answer from true to false. In pseudocode: function FIND-SUBSET-SUM(set S) if not(SUBSET-SUM(S)) return {} for each x in S if SUBSET-SUM(S – {x}) S := S – {x} return S Another well-known NP-equivalent problem is the traveling salesman problem. (en)
- Em complexidade computacional, a classe de complexidade NP-equivalente é a classe de problemas que são tanto NP-fácil quanto NP-difícil. . Por exemplo, o problema ACHAR-SUBCONJUNTO-SOMA está em NP-equivalente. Dado um conjunto de números inteiros, ACHAR-SUBCONJUNTO-SOMA é o problema que consiste em encontrar algum subconjunto dos inteiros que somam zero (caso não exista tão subconjunto, o conjunto vazio deve ser retornado). Esse problema de otimização é parecido com o problema de decisão SUBCONJUNTO-SOMA. Dado uma lista de inteiros, SUBCONJUNTO-SOMA é o problema que consiste em decidir se existe algum subconjunto cujos integrantes somem zero (ou seja, esse problema retorna apenas uma de duas possíveis respostas: sim ou não. O problema ACHAR-SUBCONJUNTO-SOMA retorna um conjunto). SUBSCONJUNTO-SOMA é NP-completo. Para mostrar que ACHAR-SUBCONJUNTO-SOMA é NP-equivalente, temos que mostrar que ele é NP-difícil e NP-fácil. Claramentente vemos que esse problema é NP-difícil. Se nós tivéssemos uma caixa preta que resolvesse ACHAR-SUBCONJUNTO-SOMA em uma unidade de tempo, então seria fácil resolver SUBCONJUNTO-SOMA. Bastaria pedir a caixa preta para achar o subconjunto que soma zero e depois conferir se ela retornou um conjunto não-vazio. Esse probelma também é NP-fácil. Se nós tivéssemos uma caixa preta que resolvesse SUBCONJUNTO-SOMA em uma unidade de tempo, então nós poderíamos usá-la para resolver ACHAR-SUBCONJUNTO-SOMA. Se a caixa retornasse falso, nós retornaríamos de imediato o conjunto vazio. Caso contrário, nós visitaríamos cada elemento de modo ordenado e checaríamos se SUBCONJUNTO-SOMA ainda poderia retornar Verdadeiro após a remoção do elemento escolhido. Depois de visitar todos os elmentos, não seria possível remover qualquer elemento sem mudar a resposta da caixa preta de verdadeiro para falso. Nesse ponto o subconjunto restante deve somar zero. Em pseudocódigo: função ACHAR-SUBCONJUNTO-SOMA(conjuntoo S) se negação(SUBCONJUNTO-SOMA(S)) retorne {} para cada x em S se SUBCONJUNTO-SOMA(S - {x}) S := S - {x} retorne S Outro problema NP-equivalente bastante conhecido é o Problema do caixeiro viajante. (pt)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is foaf:primaryTopic
of | |
![[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)