| dbo:abstract
|
- Karps 21 NP-vollständige Probleme ist eine in der Komplexitätstheorie gebräuchliche Menge NP-vollständiger Rechenprobleme. (de)
- In computational complexity theory, Karp's 21 NP-complete problems are a set of computational problems which are NP-complete. In his 1972 paper, "Reducibility Among Combinatorial Problems", Richard Karp used Stephen Cook's 1971 theorem that the boolean satisfiability problem is NP-complete (also called the Cook-Levin theorem) to show that there is a polynomial time many-one reduction from the boolean satisfiability problem to each of 21 combinatorial and graph theoretical computational problems, thereby showing that they are all NP-complete. This was one of the first demonstrations that many natural computational problems occurring throughout computer science are computationally intractable, and it drove interest in the study of NP-completeness and the P versus NP problem. (en)
- En teoría de complejidad computacional, los veintiún (21) problemas NP-completos de Karp son un conjunto de problemas computacionales famosos, que tratan sobre combinatoria y teoría de grafos y que cumplen la característica en común de que todos ellos pertenecen a la clase de complejidad de los NP-completos. La demostración fue elaborada en 1972 por el informático teórico Richard Karp, en su trabajo seminal "Reducibility Among Combinatorial Problems" (Reducibilidad entre Problemas Combinatorios), como profundización del trabajo de Stephen Cook, quien en 1971 había demostrado uno de los resultados más importantes y pioneros de la complejidad computacional: la NP-completitud del problema de satisfacibilidad booleana. El descubrimiento de Karp de que todos estos importantes problemas eran NP-completos motivó el estudio de la NP-completitud y de la indagación en la famosa pregunta, de si P = NP. (es)
- Nella teoria della complessità computazionale, i 21 problemi NP-completi di Karp sono un insieme di problemi computazionali che si presentano NP-completi. Nel suo saggio del 1972, Reducibility Among Combinatorial Problems ("Riducibilità tra problemi combinatori"), Richard Karp usò il teorema del 1971 di Stephen Cook secondo cui il problema di soddisfacibilità booleana è NP-completo (chiamato anche teorema di Cook-Levin) per mostrare che c'è una in tempo polinomiale dal problema di soddisfacibilità booleana a ciascuno dei 21 problemi computazionali di combinatoria e teoria dei grafi, mostrando in tal modo che sono tutti NP-completi. Questa fu una delle prime dimostrazioni che molti problemi computazionali naturali che si presentano in tutta l'informatica sono intrattabili computazionalmente. Questa dimostrazione attirò interesse sullo studio della NP-completezza e sulle ricerche intorno al celebre problema P = NP. (it)
- Les 21 problèmes NP-complets de Karp ont marqué une étape importante de l'histoire de la théorie de la complexité des algorithmes. Ce sont 21 problèmes réputés difficiles de combinatoire et de théorie des graphes qui sont réductibles entre eux. C'est ce qu'a démontré Richard Karp en 1972 dans son article Reducibility Among Combinatorial Problems, de même que leur NP-complétude. (fr)
- Karps 21 NP-volledige problemen zijn 21 problemen uit de theoretische computerwetenschap, hoofdzakelijk op het gebied van grafentheorie en combinatoriek, waarvan Richard Karp van de Universiteit van Californië - Berkeley in een paper uit 1972 aantoonde dat ze NP-volledig zijn. Van het eerste van deze problemen, het vervulbaarheidsprobleem, had Stephen Cook van de universiteit van Toronto in 1971 de NP-volledigheid aangetoond. Karp steunde hierop en bewees dat elk van de andere problemen kan gereduceerd worden tot het vervulbaarheidsprobleem en er dus mee equivalent is. De 21 problemen, met de benamingen die Karp ervoor gebruikte, zijn: 1.
* SATISFIABILITY - vervulbaarheidsprobleem 2.
* 0-1 INTEGER PROGRAMMING - zie Geheeltallige programmering 3.
* CLIQUE - Clique 4.
* SET PACKING- 5.
* NODE COVER - Knopenbedekking 6.
* SET COVERING - Verzamelingenoverdekking 7.
* FEEDBACK NODE SET - 8.
* FEEDBACK ARC SET - 9.
* DIRECTED HAMILTON CIRCUIT - Hamiltonpad 10.
* UNDIRECTED HAMILTON CIRCUIT- Hamiltonpad 11.
* SATISFIABILITY WITH AT MOST 3 LITERALS PER CLAUSE - 12.
* CHROMATIC NUMBER - Chromatisch getal 13.
* CLIQUE COVER - Clique 14.
* EXACT COVER - Exacte overdekking 15.
* HITTING SET - 16.
* STEINER TREE - Steinerboomprobleem 17.
* 3-DIMENSIONAL MATCHING - 18.
* KNAPSACK - Knapzakprobleem 19.
* JOB SEQUENCING - Job sequencing 20.
* PARTITION - Partitieprobleem 21.
* MAX CUT - Maximale snede (nl)
- Na teoria da complexidade computacional, os 21 problemas NP-completos de Karp é um conjunto de problemas computacionais que são NP-completos. Em seu artigo de 1972, "Reducibility Among Combinatorial Problems", Richard Karp usou o teorema de que o problema da satisfatibilidade é NP-completo de Stephen Cook publicado em 1971,(também chamado teorema de Cook-Levin), para mostrar que existe uma redução por mapeamento em tempo polinomial do problema de satisfatibilidade para cada uma das 21 dos problemas computacionais de combinatória e da teoria dos grafos, mostrando assim que todos eles são NP-completos. Esta foi uma das primeiras demonstrações de que muitos problemas computacionais naturais que ocorrem ao longo da ciência da computação são computacionalmente intratáveis, e aumentou o interesse no estudo da NP-completude e do problema "P vs NP". (pt)
- Список Карпа — список, що складається з формулювання та доведення NP-повноти 21 задачі, опублікований Річардом Карпом у 1972 році у своїй праці «Зводимість між комбінаторними задачами» (англ. «Reducibility Among Combinatorial Problems»). (uk)
- 在計算複雜度理論內，一個極度重要的成就是史提芬·古克在1971年證明出了第一個NP-完全問題— 布爾可滿足性問題。在1972年，理查德·卡普將這個想法往前推進，發表了他著名的論文"Reducibility Among Combinatorial Problems"，其內證明了21個不同的，均因為其難解而惡名昭彰的組合數學與圖論問題，是NP-完全問題。 藉由展示出許多研究上面重要的問題是NP-完全問題，卡普促進了研究NP，NP-完備性，以及現在著名的P = NP這些問題。 (zh)
- Список Карпа — список, состоящий из формулировки и доказательства NP-полноты 21 задачи, опубликованный Ричардом Карпом в 1972 году в своём труде «Возможность редукции в комбинаторных задачах» (англ. «Reducibility Among Combinatorial Problems») . (ru)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 4916 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Karps 21 NP-vollständige Probleme ist eine in der Komplexitätstheorie gebräuchliche Menge NP-vollständiger Rechenprobleme. (de)
- In computational complexity theory, Karp's 21 NP-complete problems are a set of computational problems which are NP-complete. In his 1972 paper, "Reducibility Among Combinatorial Problems", Richard Karp used Stephen Cook's 1971 theorem that the boolean satisfiability problem is NP-complete (also called the Cook-Levin theorem) to show that there is a polynomial time many-one reduction from the boolean satisfiability problem to each of 21 combinatorial and graph theoretical computational problems, thereby showing that they are all NP-complete. This was one of the first demonstrations that many natural computational problems occurring throughout computer science are computationally intractable, and it drove interest in the study of NP-completeness and the P versus NP problem. (en)
- Les 21 problèmes NP-complets de Karp ont marqué une étape importante de l'histoire de la théorie de la complexité des algorithmes. Ce sont 21 problèmes réputés difficiles de combinatoire et de théorie des graphes qui sont réductibles entre eux. C'est ce qu'a démontré Richard Karp en 1972 dans son article Reducibility Among Combinatorial Problems, de même que leur NP-complétude. (fr)
- Список Карпа — список, що складається з формулювання та доведення NP-повноти 21 задачі, опублікований Річардом Карпом у 1972 році у своїй праці «Зводимість між комбінаторними задачами» (англ. «Reducibility Among Combinatorial Problems»). (uk)
- 在計算複雜度理論內，一個極度重要的成就是史提芬·古克在1971年證明出了第一個NP-完全問題— 布爾可滿足性問題。在1972年，理查德·卡普將這個想法往前推進，發表了他著名的論文"Reducibility Among Combinatorial Problems"，其內證明了21個不同的，均因為其難解而惡名昭彰的組合數學與圖論問題，是NP-完全問題。 藉由展示出許多研究上面重要的問題是NP-完全問題，卡普促進了研究NP，NP-完備性，以及現在著名的P = NP這些問題。 (zh)
- Список Карпа — список, состоящий из формулировки и доказательства NP-полноты 21 задачи, опубликованный Ричардом Карпом в 1972 году в своём труде «Возможность редукции в комбинаторных задачах» (англ. «Reducibility Among Combinatorial Problems») . (ru)
- En teoría de complejidad computacional, los veintiún (21) problemas NP-completos de Karp son un conjunto de problemas computacionales famosos, que tratan sobre combinatoria y teoría de grafos y que cumplen la característica en común de que todos ellos pertenecen a la clase de complejidad de los NP-completos. La demostración fue elaborada en 1972 por el informático teórico Richard Karp, en su trabajo seminal "Reducibility Among Combinatorial Problems" (Reducibilidad entre Problemas Combinatorios), como profundización del trabajo de Stephen Cook, quien en 1971 había demostrado uno de los resultados más importantes y pioneros de la complejidad computacional: la NP-completitud del problema de satisfacibilidad booleana. (es)
- Nella teoria della complessità computazionale, i 21 problemi NP-completi di Karp sono un insieme di problemi computazionali che si presentano NP-completi. Nel suo saggio del 1972, Reducibility Among Combinatorial Problems ("Riducibilità tra problemi combinatori"), Richard Karp usò il teorema del 1971 di Stephen Cook secondo cui il problema di soddisfacibilità booleana è NP-completo (chiamato anche teorema di Cook-Levin) per mostrare che c'è una in tempo polinomiale dal problema di soddisfacibilità booleana a ciascuno dei 21 problemi computazionali di combinatoria e teoria dei grafi, mostrando in tal modo che sono tutti NP-completi. Questa fu una delle prime dimostrazioni che molti problemi computazionali naturali che si presentano in tutta l'informatica sono intrattabili computazionalment (it)
- Karps 21 NP-volledige problemen zijn 21 problemen uit de theoretische computerwetenschap, hoofdzakelijk op het gebied van grafentheorie en combinatoriek, waarvan Richard Karp van de Universiteit van Californië - Berkeley in een paper uit 1972 aantoonde dat ze NP-volledig zijn. Van het eerste van deze problemen, het vervulbaarheidsprobleem, had Stephen Cook van de universiteit van Toronto in 1971 de NP-volledigheid aangetoond. Karp steunde hierop en bewees dat elk van de andere problemen kan gereduceerd worden tot het vervulbaarheidsprobleem en er dus mee equivalent is. (nl)
- Na teoria da complexidade computacional, os 21 problemas NP-completos de Karp é um conjunto de problemas computacionais que são NP-completos. Em seu artigo de 1972, "Reducibility Among Combinatorial Problems", Richard Karp usou o teorema de que o problema da satisfatibilidade é NP-completo de Stephen Cook publicado em 1971,(também chamado teorema de Cook-Levin), para mostrar que existe uma redução por mapeamento em tempo polinomial do problema de satisfatibilidade para cada uma das 21 dos problemas computacionais de combinatória e da teoria dos grafos, mostrando assim que todos eles são NP-completos. Esta foi uma das primeiras demonstrações de que muitos problemas computacionais naturais que ocorrem ao longo da ciência da computação são computacionalmente intratáveis, e aumentou o inter (pt)
|
| rdfs:label
|
- Karps 21 NP-vollständige Probleme (de)
- Veintiún problemas NP-completos de Karp (es)
- 21 problemi NP-completi di Karp (it)
- 21 problèmes NP-complets de Karp (fr)
- Karp's 21 NP-complete problems (en)
- Karps 21 NP-volledige problemen (nl)
- 21 problemas NP-completos de Karp (pt)
- 21 NP-полная задача Карпа (ru)
- 卡普的二十一個NP-完全問題 (zh)
- 21 NP-повна задача Карпа (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is foaf:primaryTopic
of | |
