Эффективный универсальный решатель проблем?

12

Определение «проблемы» , чтобы быть алгоритм принимает натуральное число и возвращает 0 или 1 , который возвращает 1 , по меньшей мере , одной п N . Любое такое n называется «решением» AA1nNnA

Определите «универсальный решатель проблем» как алгоритм принимающий проблему и возвращающий одно из ее решений. Например, U может работать, циклически перебирая все натуральные числа и выполняя свой ввод для них до тех пор, пока не будет получен 1 результат (он должен остановиться только на допустимом вводе)UU1

Я заинтересован в изучении границ производительности на универсальных решениях проблем

Учитывая, что является универсальным решателем проблем, а A - проблемой, обозначим t ( U , A ) время, которое требуется U для получения вывода при принятии ввода AUAt(U,A)UA

Универсальный решатель задач называется «эффективным», когда для любого универсального решателя проблем V имеемUV

t(U,A)<t(V,A)+tV

Здесь зависит от V, но не зависит от AtVVA

Существуют ли эффективные универсальные решения проблем?

РЕДАКТИРОВАТЬ: я понял, что можно изменить определения «проблема» и «универсальный решатель проблем» в нечто более элегантное и по существу эквивалентное. «Проблема» - это алгоритм без ввода, возвращающий 0 или 1 (который останавливается). «Универсальный решатель проблем» - это алгоритм, принимающий проблему и возвращающий ее результат. Это более или менее универсальная машина Тьюринга

Старое определение может быть сведено к новому определению, поскольку, учитывая проблему в старом смысле, мы можем построить проблему B в новом смысле, который просто применяет тривиальный универсальный решатель старых проблем к A (решателю, описанному в тексте выше). )ABA

Новое определение может быть сведено к старому определению, поскольку, учитывая проблему в новом смысле, мы можем построить проблему A в старом смысле, которая просто вычисляет B и сравнивает входные данные с результатом.BAB

Тривиальным примером универсального решения проблем в новом смысле является алгоритм, который просто выполняет ввод

Ванесса
источник

Ответы:

5

Не существует эффективного универсального решения проблем. Интуитивно понятно, что U должен иметь (почти) оптимальное время выполнения для любой решаемой задачи решения; в то время как теорема об ускорении говорит, что существуют разрешимые задачи решения, у которых нет оптимального алгоритма (даже в очень мягком смысле). Чтобы формализовать это:

gSSDTIME(t)SDTIME(t)tg(t(n))<t(n)

Ug(n)=22nASAiAi=A(i)U~(i)=U(Ai)AAiO(logi)BS22TIME(B)<TIME(U~)2TIME(B)<TIME({U(Ai)})

VAiB(i)A(i)B(i)

cAit(U,Ai)>t(V,Ai)+c

U

[1] Одед Голдрайх, Вычислительная сложность, Концептуальная перспектива, теорема 4.8. Глава 4.2.1.2 также актуальна.

Рухолла Маджоддин
источник
Отличное решение, спасибо!
Ванесса
12

t(U,A)<sVt(V,A)+tVsV1

AsV

Юваль Фильмус
источник
1
U
1
sVV
sVtVV
1
Я не понимаю как. Кстати, если бы я добавил, что условие V является универсальным решателем проблем, то можно было бы исключить зависимый член A, запустив только те алгоритмы, которые могут оказаться универсальными решателями проблем
Ванесса