In computational complexity theory, the set splitting problem is the following decision problem: given a family F of subsets of a finite set S, decide whether there exists a partition of S into two subsets S1, S2 such that all elements of F are split by this partition, i.e., none of the elements of F is completely in S1 or S2. Set Splitting is one of Garey & Johnson's classical NP-complete problems. The problem is sometimes called hypergraph 2-colorability.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Problema de la división de un conjunto (es)
- Set splitting problem (en)
- Problema da divisão de conjuntos (pt)
|
| rdfs:comment
| - In computational complexity theory, the set splitting problem is the following decision problem: given a family F of subsets of a finite set S, decide whether there exists a partition of S into two subsets S1, S2 such that all elements of F are split by this partition, i.e., none of the elements of F is completely in S1 or S2. Set Splitting is one of Garey & Johnson's classical NP-complete problems. The problem is sometimes called hypergraph 2-colorability. (en)
- Em teoria da complexidade computacional, o problema da Divisão de Conjuntos é o seguinte problema de decisão:dada uma família F de subconjuntos de um conjunto finito S, decidir se existe uma partição de S em dois subconjuntos Sl, S2 de tal modo que todos os elementos de F são divididos por esta partição, i.e., nenhum dos elementos de F está completamente em S1 ou S2. A divisão de conjuntos é um dos problemas de . (pt)
- En complejidad computacional, el problema de división de un conjunto (más comúnmente conocido en inglés como Set splitting problem) es el siguiente problema de decisión: dada una familia F de subconjuntos de un conjunto finito S, ¿existe una partición de S en dos subconjuntos S1 y S2 tales que ninguno de los elementos de F esté completamente en S1 o S2? Este problema es NP-completo. (es)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - En complejidad computacional, el problema de división de un conjunto (más comúnmente conocido en inglés como Set splitting problem) es el siguiente problema de decisión: dada una familia F de subconjuntos de un conjunto finito S, ¿existe una partición de S en dos subconjuntos S1 y S2 tales que ninguno de los elementos de F esté completamente en S1 o S2? Este problema es NP-completo. Visto como un problema de optimización, se llama el problema de división del máximo conjunto (en inglés Max Set Splitting) y consiste en encontrar la partición que maximiza el número de elementos divididos de F. Este es un problema (y NP-hard). El problema sigue siendo NP-hard incluso si todos los subconjuntos de F contienen el mismo número de elementos, todos ellos mayores que 1. Como problema de decisión, el Max Set Splitting, también llamado "Set Splitting" queda como sigue: dado un número entero k, ¿existe una partición de S que divida al menos k subconjuntos de F? Si k toma el valor de un parámetro dado, luego el "Set Splitting" posee complejidad parametrizada, es decir existe un algoritmo polinómico para cualquier valor de k. (es)
- In computational complexity theory, the set splitting problem is the following decision problem: given a family F of subsets of a finite set S, decide whether there exists a partition of S into two subsets S1, S2 such that all elements of F are split by this partition, i.e., none of the elements of F is completely in S1 or S2. Set Splitting is one of Garey & Johnson's classical NP-complete problems. The problem is sometimes called hypergraph 2-colorability. (en)
- Em teoria da complexidade computacional, o problema da Divisão de Conjuntos é o seguinte problema de decisão:dada uma família F de subconjuntos de um conjunto finito S, decidir se existe uma partição de S em dois subconjuntos Sl, S2 de tal modo que todos os elementos de F são divididos por esta partição, i.e., nenhum dos elementos de F está completamente em S1 ou S2. A divisão de conjuntos é um dos problemas de . (pt)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
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)