| Arabic |
| lexicalization | ara: مسألة NP كاملة |
| lexicalization | ara: مسائل NP كاملة |
| Catalan |
| has gloss | cat: En complexitat computacional, el conjunt de problemes NP-complets representa el subconjunt de problemes de tipus NP més difícils de resoldre. Aquesta classificació és deguda a que: * Qualsevol problema de tipus NP es pot reduir a un problema de tipus NP-complet. * Com a conseqüència, trobar una solució en temps polinòmic a un problema NP-complet resoldria qualsevol problema NP en temps polinòmic, resolent el problema P=NP. |
| lexicalization | cat: Np-complet |
| Czech |
| has gloss | ces: NP-úplné (NP-complete, NPC) problémy jsou takové nedeterministicky polynomiální problémy, na které jsou polynomiálně redukovatelné všechny ostatní problémy z NP. To znamená, že třídu NP-úplných úloh tvoří v jistém smyslu ty nejtěžší úlohy z NP. Pokud by byl nalezen deterministický polynomiální algoritmus pro nějakou NP-úplnou úlohu, znamenalo by to, že všechny nedeterministicky polynomiální problémy jsou řešitelné v polynomiálním čase, tedy že třída NP se „zhroutí“ do třídy P (NP = P). Otázka, zda nějaký takový algoritmus existuje, zatím nebyla rozhodnuta, předpokládá se však, že NP ≠ P (je však zřejmé, že P ⊆ NP). Více o tomto problému najdete v článku Problém P versus NP. |
| lexicalization | ces: NP úplnost |
| lexicalization | ces: NP-úplnost |
| lexicalization | ces: NP-úplné problémy |
| Danish |
| has gloss | dan: Inden for kompleksitetsteori i datalogi, er kompleksitetsklassen NP-komplet (forkortet NP-C eller NPC, hvor NP står for non-deterministisk polynomial tid) en klasse af problemer der har følgende to egenskaber: |
| lexicalization | dan: NP-komplet |
| German |
| has gloss | deu: Der Begriff NP-Vollständigkeit (nichtdeterministisch polynomielle Vollständigkeit) ist ein Begriff aus der Komplexitätstheorie der Theoretischen Informatik, der im Jahre 1971 von Stephen A. Cook durch den Satz von Cook eingeführt wurde. Er zeichnet spezielle formale Sprachen der Komplexitätsklasse NP aus. So werden solche Sprachen NP-vollständig genannt, die – intuitiv gesprochen – die vollständige Schwierigkeit aller Sprachen aus der Komplexitätsklasse NP in sich tragen. |
| lexicalization | deu: NP-Vollständigkeit |
| Finnish |
| has gloss | fin: Laskettavuusteoriassa NP-täydelliset ongelmat ovat laskennallisesti erittäin vaativia ongelmia. Ne ovat luokan NP (epädeterministisellä Turingin koneella polynomiaalisessa ajassa ratkeavien ongelmien joukko) vaikeimmat ongelmat. Polynomiaikaisen ratkaisun löytyminen NP-täydelliseen ongelmaan deterministisellä Turingin koneella (tai millä tahansa nykyisellä tietokoneella) johtaisi polynomiaikaisen ratkaisun olemassaoloon kaikille muillekin luokan NP ongelmille. Tämä tarkoittaisi sitä, että P=NP, eli kaikki epädeterministisellä Turingin koneella polynomiaalisessa ajassa ratkeavat ongelmat ovat myös deterministisellä Turingin koneella polynomiaalisessa ajassa ratkeavia. |
| lexicalization | fin: NP-täydellisyys |
| Hebrew |
| lexicalization | heb: בעיה NP שלמה |
| lexicalization | heb: בעיה NP-שלמה |
| lexicalization | heb: בעיות NP-שלמות |
| Italian |
| has gloss | ita: :Questa pagina fornisce una descrizione tecnica dei problemi NP-completi. Per una introduzione divulgativa, vedi Classi di complessità P ed NP. |
| lexicalization | ita: NP-Completo |
| Japanese |
| has gloss | jpn: NP完全問題（エヌピーかんぜんもんだい、NP-complete problem）は、クラスNP（Non-deterministic Polynomial）に属する問題でかつ、クラスNPのすべての問題から多項式時間帰着可能な問題である。すなわち、NPに属する問題のうちでNP困難なものである。クラスNPに含まれる問題で、あるNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の多くがこの定理によって充足可能性問題より導かれたものである。充足可能性問題がNP完全であることは1971年、スティーブン・クックによって証明された。 |
| lexicalization | jpn: NP完全問題 |
| Korean |
| has gloss | kor: NP-완전(NP-complete, NP-C, NPC)은 NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합으로, 모든 NP 문제를 다항 시간 내에 NP-완전 문제로 환산할 수 있다. NP-완전 문제 중 하나라도 P에 속한다는 것을 증명한다면 모든 NP 문제가 P에 속하기 때문에, P-NP 문제가 P=NP의 형태로 풀리게 된다. 반대로 NP-완전 문제 중의 하나가 P에 속하지 않는다는 것이 증명된다면 P=NP에 대한 반례가 되어 P-NP 문제는 P≠NP의 형태로 풀리게 된다. |
| lexicalization | kor: NP-완전 문제 |
| lexicalization | kor: NP-완전 |
| Dutch |
| has gloss | nld: NP-volledigheid is een concept uit de complexiteitstheorie. Het is een beschrijving van het inzicht uit de jaren 70 dat er een bepaald verband is tussen de complexiteit van een groot aantal problemen die in de wiskunde en informatica als "moeilijk" worden beschouwd. |
| lexicalization | nld: NP-volledig probleem |
| lexicalization | nld: NP-volledig |
| Norwegian Nynorsk |
| has gloss | nno: NP-komplett er eit omgrep innan matematikken som står for «Non-Polynomial in Time Complete». NP-komplette problem er dei problema i NP som det er «vanskeligast» å finne effektive algoritmar for. Viss ein finn ein algoritme med polynomisk køyretid for eit NP-komplett problem, tyder det at alle problem i NP kan løysast med algoritmar med polynomisk køyretid, det vil seie at P=NP. Det er ikkje kjend om det er mogleg. |
| lexicalization | nno: NP-komplett |
| Polish |
| has gloss | pol: Problem NP-zupełny (NPC) czyli problem zupełny w klasie NP ze względu na redukcje wielomianowe, to problem, który należy do klasy NP oraz dowolny problem należący do NP może być do niego zredukowany w czasie wielomianowym. Czasami zamiast redukcji w czasie wielomianowym używa się redukcji w pamięci logarytmicznej. Pytanie, czy są to definicje równoważne pozostaje pytaniem otwartym . Taka definicja problemów NP-zupełnych implikuje fakt, że jeśli tylko potrafimy rozwiązać jakikolwiek problem NP-zupełny w czasie wielomianowym, to potrafimy rozwiązać w czasie wielomianowym wszystkie problemy NP. Problemy NP-zupełne można więc traktować jako najtrudniejsze problemy klasy NP (z punktu widzenia wielomianowej rozwiązywalności). |
| lexicalization | pol: Problem NP zupełny |
| lexicalization | pol: Problem NP-zupełny |
| Portuguese |
| has gloss | por: Na teoria da complexidade computacional, a classe de complexidade NP-completo é o subconjunto dos problemas de decisão em NP de tal modo que todo problema em NP se pode reduzir, com uma redução de tempo polinomial, a um dos problemas NP-completo. Pode-se dizer que os problemas de NP-completo são os problemas mais difíceis de NP e muito provavelmente não formem parte da classe de complexidade P. A razão é que se conseguisse encontrar uma maneira de resolver qualquer problema NP-completo rapidamente (em tempo polinomial) , então poderia ser utilizado algoritmos para resolver todos problemas NP rapidamente. Como exemplo de um problema NP-completo está o problema da soma dos subconjuntos que pode ser enunciado conforme segue: dado um conjunto S de inteiros, determine se há algum conjunto não vazio de S cujos elementos somem zero. É fácil de verificar se uma resposta é correta, mas não se conhece uma solução significativamente mais rápida para resolver este problema do que testar todos os subconjuntos possíveis, até encontrar um que cumpra com a condição. |
| lexicalization | por: Np completo |
| lexicalization | por: NP-completo |
| Russian |
| has gloss | rus: В теории алгоритмов NP-полная задача — это такая задача из класса NP, к которой можно свести любую другую задачу из класса NP. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро». |
| lexicalization | rus: NP-полная задача |
| lexicalization | rus: NP-полные задачи |
| Slovak |
| has gloss | slk: NP-úplný problém je taký problém, ktorý patrí do NP (je vypočítateľný v nedeterministickom polynomiálnom čase) a ľubovoľný iný problém z NP je na naň deterministicky polynomiálne redukovateľný (tzn. je NP-ťažký). NP-úplné problémy v istom zmysle reprezentujú tie najťažšie spomedzi množiny NP. Pokiaľ by niekto našiel deterministický polynomiálny algoritmus pre ľubovoľný NP-úplný problém, vďaka existujúcej redukcii by boli všetky problémy z NP riešiteľné v polynomiálnom deterministickom čase (P=NP). Takýto algoritmus doposiaľ nebol nájdený a väčšina odborníkov sa prikláňa k názoru, že neexistuje. |
| lexicalization | slk: NP-úplný problém |
| Castilian |
| has gloss | spa: En teoría de la complejidad computacional, la clase de complejidad NP-completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completo. Se puede decir que los problemas de NP-completo son los problemas más difíciles de NP y muy probablemente no formen parte de la clase de complejidad P. La razón es que de tenerse una solución polinómica para un problema de NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico (y por lo tanto, si se demuestra que para un problema NP-completo no existe solución en tiempo polinómico, ninguno de los problemas NP tendrá solución). |
| lexicalization | spa: NP completo |
| lexicalization | spa: NP-completo |
| lexicalization | spa: Problema NP-completo |
| lexicalization | spa: Problemas NP-completos |
| Serbian |
| has gloss | srp: У теорији комплексности, НП-комплетни проблеми су најтежи проблеми у класи НП (недетерминистички, полиномијално време) у смислу да су најмања подкласа НП, која би евентуално могла да остане изван класе П (још увек се не зна да ли су класе П и НП једнаке). Разлог је што би детерминистичко решење било ког НП-комплетног проблема у полиномијалном времену било такође решење сваког проблема из класе НП. Класа комплексности која се састоји од свих НП-комплетних проблема се понекад назива НП-Ц. Формалнија дефиниција је дата ниже. |
| lexicalization | srp: НП комплетни проблеми |
| lexicalization | srp: НП-комплетни проблеми |
| Swedish |
| has gloss | swe: NP-fullständiga problem (på engelska NP complete, från nondeterministic polynomial) är en klass av matematiska problem för vilka effektiva lösningar saknas. Den enda lösningen man funnit på ett godtyckligt NP-fullständigt problem är i princip att gå igenom alla tänkbara lösningar och jämföra dem, vilket är ogörligt för andra än små probleminstanser. |
| lexicalization | swe: NP-fullständig |
| lexicalization | swe: NP-kompletta problem |
| Thai |
| has gloss | tha: ในทางทฤษฎีความซับซ้อนในการคำนวณ เอ็นพีบริบูรณ์ เป็นกลุ่มความซับซ้อนที่ยากที่สุดในเอ็นพี ในแง่ที่ว่าเป็นกลุ่มปัญหาที่ไม่น่าจะมีอัลกอริทึมที่มีประสิทธิภาพได้ เพราะว่าการที่มีอัลกอริทึมที่มีประสิทธิภาพสำหรับปัญหาใดปัญหาหนึ่งในเอ็นพีบริบูรณ์ ส่งผลให้เราสามารถแก้ปัญหาทั้งหมดในกลุ่มเอ็นพีได้อย่างมีประสิทธิภาพ กลุ่มความซับซ้อนเอ็นพีบริบูรณ์ในบางครั้งถูกเรียกสั้น ๆ ว่า NP-C |
| lexicalization | tha: เอ็นพีบริบูรณ์ |
| Turkish |
| lexicalization | tur: NP-tam problemleri |
| Ukrainian |
| has gloss | ukr: NP-повна задача — в теорії алгоритмів та теорії складності це задача, що належить до класу NP та всі задачі з класу NP можна звести до неї за поліноміальний час. |
| lexicalization | ukr: NP-повна задача |
| Vietnamese |
| lexicalization | vie: Bài toán NP-đủ |
| Chinese |
| has gloss | zho: 在計算複雜度理論的世界中，NPC問題，又稱NP完全問題或NP完備問題，是NP（非決定性多項式時間）中最難的決定性問題。因此NP完備問題應該是最不可能被化簡為P（多項式時間可決定）的決定性問題的集合。許多人推測P與NPC沒有交集。理由是因若任何NPC問題得到多項式時間的解法，那此解法就可應用在所有NP問題上。更詳細的定義容下敘述。 |
| lexicalization | zho: NP-完全 |
| lexicalization | zho: NP完全问题 |
| lexicalization | zho: NP完全 |
