Почему линейное время сводимо важно

Question

При доказательстве нижней границы новой задачи путем уменьшения существующей проблемы известной сложности акцент делается на линейном сокращении времени. Я отчасти предполагаю, что для большего, чем линейного времени (скажем, омега n ^ 2, который больше линейного омега n), мы не можем сравнить две проблемы. Но как сказать это формально.

Также, скажем, известной проблемой является omega n ^ 3. Будет ли сокращение омега n ^ 2 безопасно доказывать, что неизвестная проблема имеет сложность n ^ 3?

Answer 1

Вот формальное утверждение.

Предположим, что проблема типа A может быть решена за время O(f(n).

Предположим, что проблема B может быть сведена во времени O(g(n)) к проблеме. размером h(n).

Тогда мы сможем решить проблему B во времени O(g(n) + f(h(n))).

В идеале мы хотим, чтобы сокращение было быстрым, и чтобы проблема не была слишком большой , Как правило, вы не можете добиться большего успеха, чем линейное сокращение времени, поскольку для решения проблемы требуется линейное время. Вот почему это идеал.

Обратите внимание, что если f(n) имеет верхнюю границу полинома, то «проблема размера h(n)» может быть смягчена до «проблемы размера O(h(n))». Это часто так и экономит много усилий. Однако пример, где такое упрощение не работает, это f(n) = 2^n и h(n) = n+log(n)).