Одной из возможных причин изучения классов сложности вычислений является понимание возможностей различных видов вычислительных ресурсов (случайность, недетерминизм, квантовые эффекты и т. Д.). Если мы посмотрим на это с этой точки зрения, то кажется, что мы можем получить одну правдоподобную...
Я понимаю, что большинство проблем тривиальны, если доступен остановившийся оракул (или, я думаю, что эквивалентно, гипер-вычисления). Однако применение аргумента, который показывает проблему остановки, для машины Тьюринга также показывает, что для оракула Тьюринга невозможно решить проблему...
Я знаю, что это глупо, но мне удалось запутаться, и мне нужна помощь, чтобы решить эту проблему Предположим, что , тогда ясно, что для каждого оракула имеем что противоречит тому, что существует некоторый оракул для которого , следовательно,P=NPP=NPP=NPAAAPA=NPAPA=NPAP^A=NP^AAAAPA≠NPAPA≠NPAP^A\neq...
Как мы можем гарантировать, что мы продолжаем делать правильные и обоснованные заявления о классах сложности при использовании машин оракула Тьюринга? В соответствии с моим пониманием (на основе определений, данных во вводных учебниках по этой теме), машины оракула Тьюринга могут определить статус...