Polynomial-time reduction
http://dbpedia.org/resource/Polynomial-time_reduction an entity of type: Software
Une réduction polynomiale est un outil d'informatique théorique, plus particulièrement de théorie de la complexité. C'est une classe particulière de réductions particulièrement importante, notamment pour le problème P = NP.
rdf:langString
多項式時間変換（たこうしきじかんへんかん、polynomial-time reduction）は計算量理論の一概念である。多項式時間帰着（たこうしきじかんきちゃく）、多項式時間還元（たこうしきじかんかんげん）ともいう。幾つか種類があるが、内容的に多対一還元であれば、「多項式時間多対一還元」「Karp 還元」などとも呼ばれる。もし内容がチューリング還元であれば、「多項式時間チューリング還元」「Cook 還元」などと呼ばれる。
rdf:langString
在计算复杂性理论中，多项式时间归约是指假设已有解决一个问题的子程序，利用它在多项式时间内（不考虑子程序运行所用时间）解决另一个问题的归约方法。如果将第一个问题转换成第二个的时间，且子程序被调用的次数都是多项式级别的，那么第一个问题可以多项式时间规约到第二个问题。 多项式时间规约证明了第一个问题不比第二个问题难。因为当第二个问题存在高效率算法时，第一个也存在。因为逆否命题，如果第一个问题没有高效率算法时，第二个也没有。计算复杂性理论中经常使用多项式时间规约来定义复杂性类和完全问题。
rdf:langString
Eine Polynomialzeitreduktion (auch polynomielle Reduktion) ist eine spezielle Form der Reduktion in der theoretischen Informatik. Zusätzlich zur Reduzierbarkeit wird hier gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann. Polynomiell beschränkte Turingreduktionen werden (nach Stephen A. Cook) auch als Cook-Reduktion bezeichnet. Meist bezieht sich der Begriff Polynomialzeitreduktion jedoch auf eine polynomiell beschränkte Many-one-Reduktion (auch Karp-Reduktion, nach Richard M. Karp).
rdf:langString
En complejidad computacional, una transformación polinómica, reducción polinómica o reducción de Karp, es una manera de relacionar dos problemas de decisión, de manera que la existencia de un algoritmo que resuelve el primer problema, garantiza inmediatamente, y a través de un tiempo polinómico, la existencia de un algoritmo que resuelve el segundo. Formalmente, sean L y M lenguajes formales sobre los alfabetos Σ y Γ, respectivamente, una transformación polinómica de L en M es una función computable: para todo elemento w de Σ*.
rdf:langString
In computational complexity theory, a polynomial-time reduction is a method for solving one problem using another. One shows that if a hypothetical subroutine solving the second problem exists, then the first problem can be solved by transforming or reducing it to inputs for the second problem and calling the subroutine one or more times. If both the time required to transform the first problem to the second, and the number of times the subroutine is called is polynomial, then the first problem is polynomial-time reducible to the second.
rdf:langString
Un linguaggio A si dice riducibile in tempo polinomiale al linguaggio B (denotato con ), se esiste una funzione calcolabile f in tempo polinomiale che permetta di convertire istanze del problema di A in istanze di B, tale che . Questa definizione è molto usata nella teoria della complessità computazionale in quanto se un problema A è riducibile in tempo polinomiale a B allora soluzioni polinomiali di B possono essere usate per risolvere polinomialmente anche A, dato che la composizione di polinomi rimane polinomiale.
rdf:langString
Na teoria da complexidade computacional uma redução em tempo polinomial é uma redução que é computável por uma máquina de turing determinística em tempo polinomial. Se isso é uma redução muitos-para-um, é chamado de redução de tempo polinomail muitos-para-um, transformação polinomial, ou redução Karp. Se é uma redução Turing, é chamado de redução Turing de tempo polinomial ou redução Cook. A redução em tempo polinomial é análoga a redução por mapeamento e redução Turing, agora restringindo a tempo polinomial a máquina de turing que executa a função de redução.
rdf:langString
Любой язык называется сводимым по Карпу к языку , если существует функция , вычисляемая за полиномиальное время, где F(x) принадлежит в том случае, если x принадлежит . Язык называется NP-трудным, если к нему сводится любой язык NP класса, и называется NP-полным, если он NP-труден и сам сводится к NP классу. Если будет алгоритм, решающий NP-полную задачу за полиномиальное время, тогда все NP-задачи относятся к классу P. Если такая функция существует, говорят, что сводима по Карпу к и пишут
rdf:langString
Будь-яка мова називається звідною за Карпом до мови , якщо існує функція , обчислювана за поліноміальний час, де F(x) належить в тому випадку, якщо x належить . Мова називається NP-складною, якщо до неї зводиться будь-яка мова класу NP, і називається NP-повною, якщо вона NP-складна і сама зводиться до класу NP. Якщо буде алгоритм, що розв'язує NP-повну задачу за поліноміальний час, тоді всі NP-задачі належать до класу P. Якщо така функція існує, кажуть, що звідна за Карпом до і пишуть
rdf:langString
rdf:langString
Polynomialzeitreduktion
rdf:langString
Transformación polinómica
rdf:langString
Réduction polynomiale
rdf:langString
Riduzione in tempo polinomiale
rdf:langString
多項式時間変換
rdf:langString
Polynomial-time reduction
rdf:langString
Redução em tempo polinomial
rdf:langString
Полиномиальная сводимость
rdf:langString
多项式时间归约
rdf:langString
Поліноміальна звідність
xsd:integer
159695
xsd:integer
1081558460
rdf:langString
Eine Polynomialzeitreduktion (auch polynomielle Reduktion) ist eine spezielle Form der Reduktion in der theoretischen Informatik. Zusätzlich zur Reduzierbarkeit wird hier gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann. Polynomiell beschränkte Turingreduktionen werden (nach Stephen A. Cook) auch als Cook-Reduktion bezeichnet. Meist bezieht sich der Begriff Polynomialzeitreduktion jedoch auf eine polynomiell beschränkte Many-one-Reduktion (auch Karp-Reduktion, nach Richard M. Karp). Polynomielle Many-one-Reduktionen werden in der Komplexitätstheorie beispielsweise verwendet, um nachzuweisen, dass eine Sprache der Komplexitätsklasse NP auch NP-vollständig ist.
rdf:langString
En complejidad computacional, una transformación polinómica, reducción polinómica o reducción de Karp, es una manera de relacionar dos problemas de decisión, de manera que la existencia de un algoritmo que resuelve el primer problema, garantiza inmediatamente, y a través de un tiempo polinómico, la existencia de un algoritmo que resuelve el segundo. Formalmente, sean L y M lenguajes formales sobre los alfabetos Σ y Γ, respectivamente, una transformación polinómica de L en M es una función computable: que puede ser calculada en tiempo polinómico en función del tamaño de la entrada, y que está definida por: para todo elemento w de Σ*. Cuando esta función f existe, se dice que "L es polinómicamente transformable en M".
rdf:langString
In computational complexity theory, a polynomial-time reduction is a method for solving one problem using another. One shows that if a hypothetical subroutine solving the second problem exists, then the first problem can be solved by transforming or reducing it to inputs for the second problem and calling the subroutine one or more times. If both the time required to transform the first problem to the second, and the number of times the subroutine is called is polynomial, then the first problem is polynomial-time reducible to the second. A polynomial-time reduction proves that the first problem is no more difficult than the second one, because whenever an efficient algorithm exists for the second problem, one exists for the first problem as well. By contraposition, if no efficient algorithm exists for the first problem, none exists for the second either. Polynomial-time reductions are frequently used in complexity theory for defining both complexity classes and complete problems for those classes.
rdf:langString
Une réduction polynomiale est un outil d'informatique théorique, plus particulièrement de théorie de la complexité. C'est une classe particulière de réductions particulièrement importante, notamment pour le problème P = NP.
rdf:langString
多項式時間変換（たこうしきじかんへんかん、polynomial-time reduction）は計算量理論の一概念である。多項式時間帰着（たこうしきじかんきちゃく）、多項式時間還元（たこうしきじかんかんげん）ともいう。幾つか種類があるが、内容的に多対一還元であれば、「多項式時間多対一還元」「Karp 還元」などとも呼ばれる。もし内容がチューリング還元であれば、「多項式時間チューリング還元」「Cook 還元」などと呼ばれる。
rdf:langString
Un linguaggio A si dice riducibile in tempo polinomiale al linguaggio B (denotato con ), se esiste una funzione calcolabile f in tempo polinomiale che permetta di convertire istanze del problema di A in istanze di B, tale che . Questa definizione è molto usata nella teoria della complessità computazionale in quanto se un problema A è riducibile in tempo polinomiale a B allora soluzioni polinomiali di B possono essere usate per risolvere polinomialmente anche A, dato che la composizione di polinomi rimane polinomiale. Nello specifico con il termine "funzione calcolabile in tempo polinomiale" s'intende una funzione risolvibile da una macchina di Turing di tempo polinomiale M arrestandosi con soltanto sul nastro, dopo aver iniziato con qualsiasi w in input.
rdf:langString
Na teoria da complexidade computacional uma redução em tempo polinomial é uma redução que é computável por uma máquina de turing determinística em tempo polinomial. Se isso é uma redução muitos-para-um, é chamado de redução de tempo polinomail muitos-para-um, transformação polinomial, ou redução Karp. Se é uma redução Turing, é chamado de redução Turing de tempo polinomial ou redução Cook. A redução em tempo polinomial é importante e muito usada porque é poderosa o bastante para realizar muitas transformações entre problemas importantes. Mas continua difícil a demonstração de reduções em tempo polinomial de problemas na classe NP-completa para problemas na classe P, que poderia resolver o problema P vs NP. Essa noção de redutibilidade é usada nas definições padrão de diversos problemas sobre classes de complexidade, como nas classes NP-completo, PSPACE-completo e EXPTIME-completo. Dentro da classe P, no entanto, as reduções em tempo polinomial são inadequadas, porque qualquer problema em P pode ser reduzido em tempo polinomial (ambos muito-para-um e Turing) a quase qualquer outro problema em P. Assim, para as classes dentro de P tais como L, NL, NC, e P em si, reduçoes log-espaço são usadas. Se um problema tem uma redução Karp para um problema em NP, isso mostra que o problema está em NP. Reduções Cook parecem ser mais poderosas do que as reduções Karp, por exemplo, qualquer problema em co-NP tem uma redução de Cook para qualquer problema NP-completo, enquanto que todos os problemas que estão em co-NP - NP (assumindo que eles existem) não terão reduções Karp para qualquer problema em NP. Enquanto este modelo é útil para a concepção de reduções, a desvantagem é que certas classes, como NP não são comprovadamente fechadas sob reduções Cook (acredita-se amplamente não serem), então ele nao é útil para provar que um problema está em NP . No entanto, eles são úteis para mostrar que os problemas estão em P e outras classes que são fechadas sob tais reduções. A redução em tempo polinomial é análoga a redução por mapeamento e redução Turing, agora restringindo a tempo polinomial a máquina de turing que executa a função de redução.
rdf:langString
Любой язык называется сводимым по Карпу к языку , если существует функция , вычисляемая за полиномиальное время, где F(x) принадлежит в том случае, если x принадлежит . Язык называется NP-трудным, если к нему сводится любой язык NP класса, и называется NP-полным, если он NP-труден и сам сводится к NP классу. Если будет алгоритм, решающий NP-полную задачу за полиномиальное время, тогда все NP-задачи относятся к классу P. Рассмотрим два языка и над алфавитами и . Сведение к по Карпу — это функция , вычислимая за полиномиальное время, такая, что . Таким образом, неформально язык «не сложнее» языка . Если такая функция существует, говорят, что сводима по Карпу к и пишут Отметим, что сведение по Карпу является частным случаем сведения по Куку. В англоязычных источниках также можно встретить название en:many-one reduction. Класс языков PSPACE — множество языков, допустимых детерминированной машиной Тьюринга с полиномиальным ограничением пространства. Класс языков NPSPACE — множество языков, допустимых недетерминированной машиной Тьюринга с полиномиальным ограничением пространства.
rdf:langString
Будь-яка мова називається звідною за Карпом до мови , якщо існує функція , обчислювана за поліноміальний час, де F(x) належить в тому випадку, якщо x належить . Мова називається NP-складною, якщо до неї зводиться будь-яка мова класу NP, і називається NP-повною, якщо вона NP-складна і сама зводиться до класу NP. Якщо буде алгоритм, що розв'язує NP-повну задачу за поліноміальний час, тоді всі NP-задачі належать до класу P. Розглянемо дві мови і над алфавітами і . Зведення до за Карпом — це функція , обчислювана за поліноміальний час, така, що . Таким чином, неформально мова «не складніше» від мови . Якщо така функція існує, кажуть, що звідна за Карпом до і пишуть Відзначимо, що зведення за Карпом є окремим випадком . У англомовних джерелах також можна зустріти назву many-one reduction. Клас мов PSPACE — множина мов, допустимих детермінованою машиною Тюрінга з поліноміальним обмеженням простору. Клас мов NPSPACE — множина мов, допустимих недетермінованою машиною Тюрінга з поліноміальним обмеженням простору.
rdf:langString
在计算复杂性理论中，多项式时间归约是指假设已有解决一个问题的子程序，利用它在多项式时间内（不考虑子程序运行所用时间）解决另一个问题的归约方法。如果将第一个问题转换成第二个的时间，且子程序被调用的次数都是多项式级别的，那么第一个问题可以多项式时间规约到第二个问题。 多项式时间规约证明了第一个问题不比第二个问题难。因为当第二个问题存在高效率算法时，第一个也存在。因为逆否命题，如果第一个问题没有高效率算法时，第二个也没有。计算复杂性理论中经常使用多项式时间规约来定义复杂性类和完全问题。
xsd:nonNegativeInteger
11249