Pseudo-polynomial time
http://dbpedia.org/resource/Pseudo-polynomial_time an entity of type: WikicatComplexityClasses
In der Komplexitätstheorie wird ein Algorithmus pseudopolynomiell genannt, wenn seine Laufzeit ein Polynom im numerischen Wert der Eingabe ist.
rdf:langString
En informatique théorique, et notamment en théorie de la complexité, un algorithme est appelé pseudo-polynomial si sa complexité en temps est un polynôme en la valeur numérique de l'entrée (mais pas nécessairement en la taille en mémoire de l'entrée).
rdf:langString
在计算理论领域中，若一个数值算法的时间复杂度可以表示为输入数值N的多项式，则称其时间复杂度为伪多项式时间。这是由于，N的值是N的位数的幂，故该算法的时间复杂度实际上应视为输入数值N的位数的幂。 一个具有伪多项式时间复杂度的NP完全问题称之为，而在P!=NP的情况下，若一个NP完全问题被证明没有伪多项式时间复杂度的解，则称之为。
rdf:langString
Pseudopolynomická časová složitost je v teorii složitosti taková časová složitost, která je vzhledem k číselné hodnotě vstupu , ale fakticky se jedná vzhledem k velikosti vstupu o . Klasickým příkladem jsou algoritmy řešící problémy z teorie čísel, například testy prvočíselnosti. Naivní implementace algoritmu se snaží zjistit, zda je zadané přirozené číslo prvočíslem, tak, že postupně zkouší dělit čísly . Na to potřebuje operací dělení, zdálo by se tedy, že se jedná o lineární závislost na vstupu. Ovšem velikostí vstupu není hodnota čísla, ale kolik zabírá místa v paměti počítače, tedy kolik má číslic. Například Mersennovu prvočíslu stačí k uložení v paměti počítače v obvyklém kódování jen 31 až 32 bitů, ale algoritmus zkusmého dělení by pro jeho prověření potřeboval přes dvě miliardy
rdf:langString
En teoría de la complejidad computacional, un algoritmo numérico se ejecuta en tiempo pseudo-polinómico si su tiempo de ejecución es polinómico en el valor numérico de la entrada, pudiendo ser este valor exponencial en el largo de la entrada, es decir, en el número de dígitos que la conforman. Un famoso problema que puede ser resuelto en tiempo pseudo-polinómico, a través de programación dinámica, es el Problema de la mochila.
rdf:langString
In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the numeric value of the input (the largest integer present in the input)—but not necessarily in the length of the input (the number of bits required to represent it), which is the case for polynomial time algorithms. In general, the numeric value of the input is exponential in the input length, which is why a pseudo-polynomial time algorithm does not necessarily run in polynomial time with respect to the input length.
rdf:langString
Dalam , algoritme numerik berjalan dalam waktu semu-polinomial jika adalah polinomial dari nilai numerik data yang dimasukkan (bilangan bulat terbesar yang ada dalam data tersebut) — dan tidak harus dalam panjang dari data yang dimasukkan (jumlah bit yang dibutuhkan untuk mewakili panjangnya), yang merupakan kasus untuk algoritme . Secara umum, nilai numerik dari data yang dimasukkan termasuk eksponensial pada panjangnya, oleh karena itu algoritme waktu semu-polinomial tidak harus berjalan dalam waktu polinomial sesuai dengan panjang masukan.
rdf:langString
In teoria della complessità computazionale, un algoritmo è detto pseudopolinomiale se la sua complessità temporale è polinomiale nel valore numerico del suo input e non necessariamente nella sua dimensione (ovvero il numero di bits necessari per la sua codifica). Se si vuole rappresentare un intero in una base sono necessari almeno bits. Perciò in genere il valore è esponenziale nella sua grandezza.
rdf:langString
Algorytm pseudowielomianowy – algorytm, którego złożoność obliczeniowa jest pseudowielomianowa. Oznacza to, że zależy ona nie tylko od rozmiaru danych wejściowych, ale również od pewnego parametru charakterystycznego dla danego problemu. Przykładowo dla problemu plecakowego istnieje algorytm pseudowielomianowy który go rozwiązuje w czasie , gdzie to rozmiar danych wejściowych, a to rozmiar plecaka. Jeśli jakikolwiek problem silnie NP-zupełny ma algorytm pseudowielomianowy, to każdy problem z klasy NP da się rozwiązać w czasie wielomianowym, tzn. P = NP.
rdf:langString
Na teoria da complexidade computacional, um algoritmo numérico é executado em tempo pseudopolinomial se o seu tempo de execução é polinomial no valor numérico da entrada, mas é exponencial no comprimento da entrada – o número de bits necessários para representá-lo.
rdf:langString
Псевдополиномиальный алгоритм — в теории сложности вычислений это полиномиальный алгоритм, проявляющий экспоненциальный характер только при очень больших значениях числовых параметров. Более строгое определение выглядит так. Пусть – некоторая функция, задающая значение числового параметра индивидуальной задачи . Если таких параметров несколько, в качестве можно взять или максимальное, или среднее значение, а если задача вовсе не имеет числовых параметров (например, раскраска графа, шахматы и т.п.), то . Алгоритм называется псевдополиномиальным, если он имеет оценку трудоемкости , где – некоторый полином от двух переменных.
rdf:langString
Псевдополіноміальний алгоритм - алгоритм, що виявляє експонентний характер складності лише при дуже великих значеннях його числових параметрів. Більш точне визначення виглядає так. Нехай M(z) - деяка функція, що задає значення числового параметра індивідуальної задачі z. Якщо таких параметрів декілька, як M(z) можна взяти або максимальне, або середнє значення, а якщо задача зовсім не має числових параметрів (наприклад, розфарбування графу, шахи тощо), то M(z) = 0. Алгоритм називається псевдополіноміальним, якщо він має оцінку складності tмакс(z) = O( P(| z |, M (z)) ), де P - деякий поліном від двох змінних.
rdf:langString
rdf:langString
Pseudopolynomická časová složitost
rdf:langString
Pseudopolynomiell
rdf:langString
Tiempo pseudo-polinómico
rdf:langString
Temps de calcul pseudo-polynomial
rdf:langString
Waktu semu-polinomial
rdf:langString
Tempo pseudopolinomiale
rdf:langString
Algorytm pseudowielomianowy
rdf:langString
Pseudo-polynomial time
rdf:langString
Tempo pseudopolinomial
rdf:langString
Псевдополиномиальный алгоритм
rdf:langString
伪多项式时间
rdf:langString
Псевдополіноміальний алгоритм
xsd:integer
3149636
xsd:integer
1090337054
rdf:langString
Pseudopolynomická časová složitost je v teorii složitosti taková časová složitost, která je vzhledem k číselné hodnotě vstupu , ale fakticky se jedná vzhledem k velikosti vstupu o . Klasickým příkladem jsou algoritmy řešící problémy z teorie čísel, například testy prvočíselnosti. Naivní implementace algoritmu se snaží zjistit, zda je zadané přirozené číslo prvočíslem, tak, že postupně zkouší dělit čísly . Na to potřebuje operací dělení, zdálo by se tedy, že se jedná o lineární závislost na vstupu. Ovšem velikostí vstupu není hodnota čísla, ale kolik zabírá místa v paměti počítače, tedy kolik má číslic. Například Mersennovu prvočíslu stačí k uložení v paměti počítače v obvyklém kódování jen 31 až 32 bitů, ale algoritmus zkusmého dělení by pro jeho prověření potřeboval přes dvě miliardy dělení. Obecně číslo potřebuje k uložení řádově bitů, zkusmé dělení tedy provede zhruba dělení, což je závislost zjevně exponenciální. Naproti tomu skutečně polynomickým algoritmem je například sčítání dlouhých čísel, kde školský algoritmus postupuje zprava číslici po číslici (se započítáním přenosu) a jeho časová složitost je tedy lineárně závislá nikoliv na hodnotě čísla, ale na počtu jeho číslic.
rdf:langString
In der Komplexitätstheorie wird ein Algorithmus pseudopolynomiell genannt, wenn seine Laufzeit ein Polynom im numerischen Wert der Eingabe ist.
rdf:langString
En teoría de la complejidad computacional, un algoritmo numérico se ejecuta en tiempo pseudo-polinómico si su tiempo de ejecución es polinómico en el valor numérico de la entrada, pudiendo ser este valor exponencial en el largo de la entrada, es decir, en el número de dígitos que la conforman. Los problemas NP-completos con algoritmos que se ejecutan en tiempo pseudo-polinómico se denominan NP-completos débiles.Un problema NP-completo se denomina NP-completo fuerte si se puede demostrar que no puede ser resuelto por algoritmos pseudo-polinómicos, salvo que se cumpla que P=NP. Las clases NP-hard débil y fuerte se definen de forma análoga. Un famoso problema que puede ser resuelto en tiempo pseudo-polinómico, a través de programación dinámica, es el Problema de la mochila.
rdf:langString
In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the numeric value of the input (the largest integer present in the input)—but not necessarily in the length of the input (the number of bits required to represent it), which is the case for polynomial time algorithms. In general, the numeric value of the input is exponential in the input length, which is why a pseudo-polynomial time algorithm does not necessarily run in polynomial time with respect to the input length. An NP-complete problem with known pseudo-polynomial time algorithms is called weakly NP-complete.An NP-complete problem is called strongly NP-complete if it is proven that it cannot be solved by a pseudo-polynomial time algorithm unless P = NP. The strong/weak kinds of NP-hardness are defined analogously.
rdf:langString
Dalam , algoritme numerik berjalan dalam waktu semu-polinomial jika adalah polinomial dari nilai numerik data yang dimasukkan (bilangan bulat terbesar yang ada dalam data tersebut) — dan tidak harus dalam panjang dari data yang dimasukkan (jumlah bit yang dibutuhkan untuk mewakili panjangnya), yang merupakan kasus untuk algoritme . Secara umum, nilai numerik dari data yang dimasukkan termasuk eksponensial pada panjangnya, oleh karena itu algoritme waktu semu-polinomial tidak harus berjalan dalam waktu polinomial sesuai dengan panjang masukan. Masalah dengan algoritme waktu semu-polinomial diketahui disebut sebagai . Masalah kelengkapan-NP baru bisa disebut jika terbukti tidak dapat diselesaikan dengan algoritme waktu semu-polinomial kecuali . Jenis yang kuat/lemah didefinisikan secara analog.
rdf:langString
In teoria della complessità computazionale, un algoritmo è detto pseudopolinomiale se la sua complessità temporale è polinomiale nel valore numerico del suo input e non necessariamente nella sua dimensione (ovvero il numero di bits necessari per la sua codifica). Se si vuole rappresentare un intero in una base sono necessari almeno bits. Perciò in genere il valore è esponenziale nella sua grandezza. Un problema NP-completo per il quale si conosce un algoritmo pseudopolinomiale che lo risolve è anche detto .È invece detto un problema NP-completo per il quale è dimostrato la non esistenza di un algoritmo pseudopolinomiale che lo risolve, a meno che P=NP.
rdf:langString
En informatique théorique, et notamment en théorie de la complexité, un algorithme est appelé pseudo-polynomial si sa complexité en temps est un polynôme en la valeur numérique de l'entrée (mais pas nécessairement en la taille en mémoire de l'entrée).
rdf:langString
Algorytm pseudowielomianowy – algorytm, którego złożoność obliczeniowa jest pseudowielomianowa. Oznacza to, że zależy ona nie tylko od rozmiaru danych wejściowych, ale również od pewnego parametru charakterystycznego dla danego problemu. Przykładowo dla problemu plecakowego istnieje algorytm pseudowielomianowy który go rozwiązuje w czasie , gdzie to rozmiar danych wejściowych, a to rozmiar plecaka. Jest to słabsze założenie co do czasu działania niż założenie dla algorytmów wielomianowych, których czas działania jest ograniczony przez wielomian od wielkości wejścia zapisanego w systemie binarnym (lub innym systemie pozycyjnym o podstawie większej od 1). Jeśli jakikolwiek problem silnie NP-zupełny ma algorytm pseudowielomianowy, to każdy problem z klasy NP da się rozwiązać w czasie wielomianowym, tzn. P = NP. Problem plecakowy jest NP-trudny i nie jest dla niego znany algorytm wielomianowy (gdyby istniał, oznaczałoby to, że P = NP). Znany jest jednak algorytm pseudowielomianowy dla tego problemu oparty na programowaniu dynamicznym.
rdf:langString
Na teoria da complexidade computacional, um algoritmo numérico é executado em tempo pseudopolinomial se o seu tempo de execução é polinomial no valor numérico da entrada, mas é exponencial no comprimento da entrada – o número de bits necessários para representá-lo. Um problema NP-completo com algoritmos tempo pseudopolinomial conhecidos é chamado fracamente NP-completo.Um problema NP-completo é chamado de fortemente NP-completo se for comprovado que ele não pode ser resolvido por um algoritmo de tempo pseudopolinomial, a menos que P=NP. Os tipos fortes/fracos de NP-difículdade são definidos de forma análoga.
rdf:langString
Псевдополиномиальный алгоритм — в теории сложности вычислений это полиномиальный алгоритм, проявляющий экспоненциальный характер только при очень больших значениях числовых параметров. Более строгое определение выглядит так. Пусть – некоторая функция, задающая значение числового параметра индивидуальной задачи . Если таких параметров несколько, в качестве можно взять или максимальное, или среднее значение, а если задача вовсе не имеет числовых параметров (например, раскраска графа, шахматы и т.п.), то . Алгоритм называется псевдополиномиальным, если он имеет оценку трудоемкости , где – некоторый полином от двух переменных. Полиномиальный алгоритм является также и псевдополиномиальным (с полиномом, не зависящим от второго аргумента), обратное же не имеет места. Псевдополиномиальные алгоритмы, формально относящиеся к экспоненциальным, на практике работают как полиномиальные во всех случаях, кроме очень больших значений числового параметра.
rdf:langString
在计算理论领域中，若一个数值算法的时间复杂度可以表示为输入数值N的多项式，则称其时间复杂度为伪多项式时间。这是由于，N的值是N的位数的幂，故该算法的时间复杂度实际上应视为输入数值N的位数的幂。 一个具有伪多项式时间复杂度的NP完全问题称之为，而在P!=NP的情况下，若一个NP完全问题被证明没有伪多项式时间复杂度的解，则称之为。
rdf:langString
Псевдополіноміальний алгоритм - алгоритм, що виявляє експонентний характер складності лише при дуже великих значеннях його числових параметрів. Більш точне визначення виглядає так. Нехай M(z) - деяка функція, що задає значення числового параметра індивідуальної задачі z. Якщо таких параметрів декілька, як M(z) можна взяти або максимальне, або середнє значення, а якщо задача зовсім не має числових параметрів (наприклад, розфарбування графу, шахи тощо), то M(z) = 0. Алгоритм називається псевдополіноміальним, якщо він має оцінку складності tмакс(z) = O( P(| z |, M (z)) ), де P - деякий поліном від двох змінних. Очевидно, що будь-який поліноміальний алгоритм є також і псевдополіноміальним (з поліномом, не залежних від другого аргументу), зворотне ж не має місця.Псевдополіноміальні алгоритми, формально пов'язані з експоненціальним, на практиці працюють як поліноміальні у всіх випадках, крім дуже великих значень числового параметра.
xsd:nonNegativeInteger
4743