我的手册有一个自我评估练习：
“显示如果X在多项式时间内减少到Y，并且X在EXP中，则Y也在EXP中”
作为练习的答案：
“如果Y在P中，则X也在P中。但是X在EXP中。所以Y在EXP中。”
我的问题：
为什么我不能争论Y是否一定不在EXP中？
在计算复杂性理论中，复杂性类
EXPTIME（有时称为EXP或DEXPTIME）是具有指数运行时的所有决策问题的集合，即可以在O(2^p(n))时间由确定性图灵机解决，其中p(n)是n的多项式函数。 。
这意味着对于被归类为EXP的问题，没有比O(2^p(n))更有效地解决它的算法。
如果你可以将X减少到Y，那么解决X的复杂性就是O(reduction + solving Y)。
如果你能够在多项式时间内将问题X的实例减少为问题Y的实例，然后在多项式时间内求解Y，则意味着你可以在多项式时间内解决X（这反过来意味着X不在EXP中，导致矛盾）。
因此，对于X是EXP，那么Y必然也必须如此。