Cart (0)Free Online Dictionary
NP-hard
| Wikipedia English The Free Encyclopedia |  Download this dictionary |
NP-hard
NP-hard (non-deterministic polynomial-time hard), in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H (i.e., L ≤ TH). In other words, L can be solved in polynomial time by an oracle machine with an oracle for H. Informally, we can think of an algorithm that can call such an oracle machine as a subroutine for solving H, and solves L in polynomial time, if the subroutine call takes only one step to compute. NP-hard problems may be of any type: decision problems, search problems, or optimization problems.
| See more at Wikipedia.org... |
© This article uses material from Wikipedia® and is licensed under the GNU Free Documentation License and under the Creative Commons Attribution-ShareAlike License
| Wikipedia Deutsch Die freie Enzyklopädie | Download this dictionary |
NP-Schwere
NP-Schwere bzw. NP-Härte (Fehlübersetzung des englischen NP-hard, abgekürzt für Non-deterministic Polynomial-time hard) ist ein Begriff aus dem Bereich der theoretischen Informatik, der zur Klassifizierung von Komplexitätsproblemen dient. Er gibt Aufschluss darüber, ob für alle Probleme aus der Komplexitätsklasse NP jeweils ein polynomieller Algorithmus existiert, der diese auf eine betrachtete formale Sprache reduziert.
| Mehr unter Wikipedia.org... |
© Dieser Eintrag beinhaltet Material aus Wikipedia und ist lizensiert auf GNU-Lizenz für freie Dokumentation
| Polska Wikipedia – Darmowa encyklopedia | Download this dictionary |
Problem NP-trudny
W teorii złożoności obliczeniowej problem NP-trudny (NPH) to taki problem obliczeniowy, którego rozwiązanie jest co najmniej tak trudne jak rozwiązanie każdego problemu z klasy NP.
Formalna definicja problemu NP-trudnego jest następująca: problem 
jest NP-trudny jeżeli pewien problem NP-zupełny 
jest do niego redukowalny wielomianową transformacją Turinga .
Innymi słowy, problem NP-zupełny można rozwiązać w wielomianowym czasie algorytmem rozwiązującym problem NP-trudny , przez wykorzystanie hipotetycznej procedury 
sprowadzającej problem NP-zupełny do problemu NP-trudnego , jeżeli tylko daje sie wykonać w wielomianowym czasie. NP-trudność można zdefiniować także w kategorii języków formalnych (a nie problemów). Do klasy problemów NP-trudnych mogą należeć problemy różnego typu: decyzyjne, przeszukiwania, optymalizacyjne.
| W celu uzyskania więcej informacji, zobacz w Wikipedia.οrg... |
© W niniejszym artykule wykorzystano materialy pochodzace z Wikipedia® i posiada on Powszechna Licencje Publiczna GNU
| Wikipedia Italiano L'enciclopedia libera | Download this dictionary |
NP-arduo
NP-arduo (Non-deterministico arduo a tempo polinomiale), è una classe di problemi della teoria della complessità computazionale definita informalmente "difficile almeno come i più ardui problemi definiti in NP".
Un problema H è NP-hard se e solo se c'è un problema NP-completo L che è riducibile polinomialmente ad H, ad esempio: 
. In altre parole, L può essere risolto in tempo polinomiale da una macchina di interpretazione dell'oracolo con un qualsiasi oracolo per H. Informalmente possiamo pensarlo come un algoritmo che può chiamare una macchina di interpretazione dell'oracolo, come subroutine per la risoluzione di H, e risolve L in tempo polinomiale se la subroutine richiede solo un passo per la sua computazione. I problemi NP-hard possono essere di qualsiasi tipologia, decisionali, di ricerca e di ottimizzazione.
| Per saperne di più visita Wikipedia.org... |
Questo articolo utilizza materiale tratto da Wikipedia® ed è autorizzato sotto la licenza GNU Free Documentation License
| Wikipedia Español La enciclopedia libre | Download this dictionary |
NP-hard
En teoría de la complejidad computacional, la clase de complejidad NP-hard (o NP-difícil) es el conjunto de los problemas de decisión que contiene los problemas H tales que todo problema L en NP puede ser transformado polinomialmente en H. Esta clase puede ser descrita como conteniendo los problemas de decisión que son al menos tan difíciles como un problema de NP. Esta afirmación se justifica porque si podemos encontrar un algoritmo A que resuelve uno de los problemas H de NP-hard en tiempo polinómico, entonces es posible construir un algoritmo que trabaje en tiempo polinómico para cualquier problema de NP ejecutando primero la reducción de este problema en H y luego ejecutando el algoritmo A.
| Ver más en Wikipedia.org... |
Este artículo utiliza contenidos de Wikipedia® y está disponible bajo los términos de la Licencia de documentación libre GNU
| NP-hard in English | NP-hard in Italian | NP-hard in Spanish | NP-hard in German | NP-hard in Japanese | NP-hard in Korean | NP-hard in Turkish | NP-hard in Hebrew | NP-hard in Polish | NP-hard in Serbian
You think you have ethics...
Take the survey NOW!