如何证明一种语言属于P类？

Question

我有两种语言：

A = { <M, w> | M accepts w after running for at most 2^500 steps }
B = { <M, w, 1^t> | M accepts w after running for at most t steps }

我需要弄清楚这些语言是否属于P类。我知道，如果一种语言在多时间内运行，它就属于P类。我很确定A语言以指数时间运行，但我不太确定像2^500这样的常量是否会导致多时间运行。

感谢您的帮助，谢谢！

Answer 1

算法时间表示为输入大小的函数。如果对于任何输入，A需要2^500步，那么它实际上是恒定时间(无论输入什么，运行时间都是恒定的)，这肯定是在P中。

B采用t个步长，其中t大概是输入的大小，所以它是线性时间(时间随着输入大小线性增加)，也是在P中。

如果您有一个问题，例如，需要2^t步或t！(阶乘)步骤，那么它不在P.查找大O符号