Полиномиальное ли время редукции?

Оглавление:

Полиномиальное ли время редукции?
Полиномиальное ли время редукции?

Видео: Полиномиальное ли время редукции?

Видео: Полиномиальное ли время редукции?
Видео: Безударные гласные в русских говорах — Игорь Исаев 2024, Ноябрь
Anonim

В теории вычислительной сложности полиномиальная редукция - это метод решения одной задачи с помощью другой. Редукции за полиномиальное время часто используются в теории сложности для определения как классов сложности, так и полных задач для этих классов. …

Что считается полиномиальным временем?

Алгоритм называется полиномиальным, если время его выполнения ограничено сверху полиномиальным выражением от размера входных данных для алгоритма, то есть T(n)=O(nk) для некоторой положительной константы k.

Как узнать, является ли что-то полиномиальным временем?

3 Ответы. Алгоритм является полиномиальным (имеет полиномиальное время работы), если для некоторого k, C>0, время его работы на входных данных размера n не превосходит Cnk. Эквивалентно, алгоритм является полиномиальным, если для некоторого k>0 время его работы на входных данных размера n равно O(nk).

Что произойдет, если редукция разрешена за экспоненциальное время?

Если сокращение допустимо экспоненциальное время, то оно может полностью решить исходную проблему и создать тривиальный экземпляр целевой проблемы Это означает, что каждая проблема в NP сводится к любой другую задачу с помощью такого типа редукции, поэтому каждая задача в NP является NP-полной для экспоненциальной редукции времени.

Что такое экспоненциальный алгоритм?

Алгоритм называется экспоненциальным по времени, если T(n) ограничено сверху 2poly( ) , где poly(n) - некоторый полином от n. Более формально алгоритм является экспоненциальным по времени, если T(n) ограничено величиной O(2nk) для некоторой константы k. Ref:Wiki.

Рекомендуемые:

Можно ли принимать пастилки от горла во время беременности?

Можно ли принимать пастилки от горла во время беременности?

Ладенцы от горла содержащие местные анестетики и антибактериальные средства можно использовать при беременности. Избегайте чрезмерного использования, так как это может вызвать нежелательные побочные эффекты, такие как диарея. Полоскание горла соленой водой или употребление продуктов с лимоном и медом также может облегчить боль в горле .

Рвота появляется во время беременности?

Рвота появляется во время беременности?

Когда возникает тошнота и рвота при беременности тошнота и рвота при беременности Утренняя тошнота, также называемая тошнотой и рвотой при беременности (НВП), является симптомом беременности, который включает тошноту или рвота. Несмотря на название, тошнота или рвота могут возникнуть в любое время суток.

Во время гальванической коррозии?

Во время гальванической коррозии?

Гальваническая коррозия возникает, когда два разнородных металла погружены в проводящий раствор и электрически соединены Один металл (катод) защищен, а другой (анод) подвергается коррозии. Скорость атаки на анод увеличивается по сравнению со скоростью, когда металл не связан .

Какое время может быть?

Какое время может быть?

“Might” - это прошедшее время от “may”. Решая, какое из них использовать, вы можете использовать время предложения, чтобы выбрать «может» или «может». Обратитесь к этим примерам, чтобы увидеть, как используется слово «может быть»: Возможно, он позвонил мне после игры, но они были заняты .

Это остаться на некоторое время или остаться на некоторое время?

Это остаться на некоторое время или остаться на некоторое время?

Он может модифицировать глагол, например, «остаться», например, «остаться некоторое время». Но вот самое сложное: именное словосочетание, которое выражает элемент времени или продолжительность, является наречием. Таким образом, «Stay a while», в котором используется существительное «пока», является правильным .