| dbo:abstract
|
- In der Komplexitätstheorie bezeichnet die Komplexitätsklasse NP-leicht die Menge aller Funktionen, die in polynomieller Zeit durch eine deterministische Turingmaschine mit Hilfe einer Orakel-Turingmaschine für ein Entscheidungsproblem aus der Klasse NP berechnet werden können. (de)
- In complexity theory, the complexity class NP-easy is the set of function problems that are solvable in polynomial time by a deterministic Turing machine with an oracle for some decision problem in NP. In other words, a problem X is NP-easy if and only if there exists some problem Y in NP such that X is polynomial-time Turing reducible to Y. This means that given an oracle for Y, there exists an algorithm that solves X in polynomial time (possibly by repeatedly using that oracle). NP-easy is another name for FPNP (see the function problem article) or for FΔ2P (see the polynomial hierarchy article). An example of an NP-easy problem is the problem of sorting a list of strings. The decision problem "is string A greater than string B" is in NP. There are algorithms such as quicksort that can sort the list using only a polynomial number of calls to the comparison routine, plus a polynomial amount of additional work. Therefore, sorting is NP-easy. There are also more difficult problems that are NP-easy. See NP-equivalent for an example. The definition of NP-easy uses a Turing reduction rather than a many-one reduction because the answers to problem Y are only TRUE or FALSE, but the answers to problem X can be more general. Therefore, there is no general way to translate an instance of X to an instance of Y with the same answer. (en)
- Dans la théorie de la complexité, un problème est NP-facile s'il est résoluble en temps polynomial par une machine de Turing déterministe avec oracle, pour un certain problème de décision dans NP. En d'autres termes, un problème X est NP-facile si et seulement si il existe un problème Y de NP tel que X est réductible en temps polynomiale à Y. Cela signifie qu'étant donné un oracle pour Y, il existe un algorithme qui résout X en temps polynomial (éventuellement en utilisant cet oracle de manière répétée). NP-facile est une autre appellation pour FPNP ou pour FΔ2P (voir l'article sur la hiérarchie polynomiale). Un exemple d'un problème NP-facile est le problème de tri d'une liste de chaînes de caractères. Le problème de décision "La chaîne A est plus longue que la chaîne B" est dans NP. Il existe des algorithmes tels que le tri rapide qui permettent de trier la liste en utilisant seulement un nombre polynomial d'appels à la routine de comparaison. Par conséquent, le tri est NP-facile. (fr)
- Em complexidade computacional, a classe de complexidade NP-fácil é a classe de problemas que são solúveis em por uma com um oráculo para algum problema de decisão em NP. Em outras palavras, um problema X é NP-fácil se e somente se existe algum problema Y em NP tal que X é redutível em tempo polinomial a Y. Isso significa que dado um oráculo para Y, existe um algoritmo que resolve X em tempo polinomial (possivelmente através do uso repetitivo dese oráculo). NP-fácil é um outro nome para FPNP ou para FΔ2P. Um exemplo de um problema NP-fácil é o problema de ordenação de uma lista de strings. O problema de decisão "a string A é maior que a string B" está em NP. Existem algoritmos como o Quicksort que podem ordenar a lista usando apenas um número polinomial de chamadas à função de comparação, além de uma quantidade polinomial de trabalhos adicionais. Portanto, ordenação é NP-fácil. Também existem problemas mais difíceis que são NP-fácil. Veja NP-equivalente para um exemplo. A definição de NP-fácil usa a redução em tempo polinomial e não a redução muitos-para-um porque as respostas do problema Y são apenas VERDADEIRO ou FALSO, mas as respostas do problema X podem ser mais abrangentes. Portanto, não existe um modo geral de traduzir uma instância de X para uma instância de Y com a mesma resposta. (pt)
- 在計算複雜度理論內，NP-易（或称“NP-容易”，NP-easy）這個複雜度類是使用帶有在NP裡面某個決定性問題神諭的圖靈機，能在多項式時間內解決掉的功能性問題。 換句話說，一個問題X屬於NP-易，若且唯若存在某個在NP裡面的問題Y，令X可以於多項式時間內圖靈歸約（polynomial-time Turing reducible）至Y。換句話說，給予一個解決Y的神諭（一個只需要單位時間就可以），則存在一個在多項式時間內解決X的演算法（可能需要藉由不斷的使用神諭，這是可以接受的）。 NP-易也是FPNP（參見功能性問題頁面）或者FΔ2P（參見頁面）的別名。 一個NP-易的例子是將一堆字串進行排序。決定型問題"字串A是否比B來的大"是一個NP問題。然後我們已經有快速排序（quicksort）或者合併排序（merge sort）這些演算法，它們只要有單位時間比較大小的方式，即可以在多項式時間之內排序一個集合。因此我們結合以上兩點可以得知，字串排序是NP-易的問題。 NP-易裡面也是有非常困難的問題。例如說，可以參考（NP-equivalent）頁面裡面的例子。 NP-易的定義上使用圖靈規約而非（many to one reduction），因為Y是決定型問題，答案只有TRUE或者FALSE，但是問題X是功能性問題，答案可以有很多種。因此，並不存在一個將X跟Y以相同答案互相轉換的方法。 (zh)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 1748 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- In der Komplexitätstheorie bezeichnet die Komplexitätsklasse NP-leicht die Menge aller Funktionen, die in polynomieller Zeit durch eine deterministische Turingmaschine mit Hilfe einer Orakel-Turingmaschine für ein Entscheidungsproblem aus der Klasse NP berechnet werden können. (de)
- 在計算複雜度理論內，NP-易（或称“NP-容易”，NP-easy）這個複雜度類是使用帶有在NP裡面某個決定性問題神諭的圖靈機，能在多項式時間內解決掉的功能性問題。 換句話說，一個問題X屬於NP-易，若且唯若存在某個在NP裡面的問題Y，令X可以於多項式時間內圖靈歸約（polynomial-time Turing reducible）至Y。換句話說，給予一個解決Y的神諭（一個只需要單位時間就可以），則存在一個在多項式時間內解決X的演算法（可能需要藉由不斷的使用神諭，這是可以接受的）。 NP-易也是FPNP（參見功能性問題頁面）或者FΔ2P（參見頁面）的別名。 一個NP-易的例子是將一堆字串進行排序。決定型問題"字串A是否比B來的大"是一個NP問題。然後我們已經有快速排序（quicksort）或者合併排序（merge sort）這些演算法，它們只要有單位時間比較大小的方式，即可以在多項式時間之內排序一個集合。因此我們結合以上兩點可以得知，字串排序是NP-易的問題。 NP-易裡面也是有非常困難的問題。例如說，可以參考（NP-equivalent）頁面裡面的例子。 NP-易的定義上使用圖靈規約而非（many to one reduction），因為Y是決定型問題，答案只有TRUE或者FALSE，但是問題X是功能性問題，答案可以有很多種。因此，並不存在一個將X跟Y以相同答案互相轉換的方法。 (zh)
- In complexity theory, the complexity class NP-easy is the set of function problems that are solvable in polynomial time by a deterministic Turing machine with an oracle for some decision problem in NP. In other words, a problem X is NP-easy if and only if there exists some problem Y in NP such that X is polynomial-time Turing reducible to Y. This means that given an oracle for Y, there exists an algorithm that solves X in polynomial time (possibly by repeatedly using that oracle). There are also more difficult problems that are NP-easy. See NP-equivalent for an example. (en)
- Dans la théorie de la complexité, un problème est NP-facile s'il est résoluble en temps polynomial par une machine de Turing déterministe avec oracle, pour un certain problème de décision dans NP. En d'autres termes, un problème X est NP-facile si et seulement si il existe un problème Y de NP tel que X est réductible en temps polynomiale à Y. Cela signifie qu'étant donné un oracle pour Y, il existe un algorithme qui résout X en temps polynomial (éventuellement en utilisant cet oracle de manière répétée). (fr)
- Em complexidade computacional, a classe de complexidade NP-fácil é a classe de problemas que são solúveis em por uma com um oráculo para algum problema de decisão em NP. Em outras palavras, um problema X é NP-fácil se e somente se existe algum problema Y em NP tal que X é redutível em tempo polinomial a Y. Isso significa que dado um oráculo para Y, existe um algoritmo que resolve X em tempo polinomial (possivelmente através do uso repetitivo dese oráculo). NP-fácil é um outro nome para FPNP ou para FΔ2P. (pt)
|
| rdfs:label
|
- NP-leicht (de)
- NP-facile (fr)
- NP-easy (en)
- NP-fácil (pt)
- NP-易 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
