полиномиальное сокращение от проблем EXP

Question

В моем руководстве есть упражнение по самооценке:

"Показать, что если X за полиномиальное время уменьшается до Y, а X в EXP, то Y также в EXP"

Как ответ на упражнение:

"если бы Y был в P, то X был бы также в P. Но X находится в EXP. Поэтому Y находится в EXP."

Мой вопрос:

Почему я не могу утверждать, не обязательно ли вообще Y в EXP?

Answer 1

В теории вычислительной сложности класс сложности EXPTIME (иногда называемый EXP или DEXPTIME) - это совокупность всех проблем решения, имеющих экспоненциальное время выполнения, т. Е. Решаемых детерминированной машиной Тьюринга в * 1005. * time, где p(n) - полиномиальная функция от n.

Это означает, что для классификации проблемы, которая относится к EXP, не существует алгоритма для ее более эффективного решения, чем O(2^p(n)).

Если вы можете уменьшить X до Y, сложность решения X будет O(reduction + solving Y).

Если вы можете свести свой экземпляр проблемы X к экземпляру задачи Y за полиномиальное время, а затем решить Y за полиномиальное время, это означает, что вы можете решить X за полиномиальное время (что, в свою очередь, означает, что X не входит в EXP, что приводит к противоречию).

Следовательно, чтобы X было EXP, тогда Y также обязательно должно быть.