我正在读这本书<
因为多项式时间算法决定的语言类别是多项式时间接受的语言类别的子集 算法，我们只需要证明如果 L 被 a 接受 多项式时间算法，由多项式时间决定 算法。设 L 是某个多项式时间接受的语言 算法A...（省略证明）...因此A是多项式时间 决定 L.
的算法
我认为这意味着如果有两个集合A和B，并且A是B的子集，并且有一个元素x∈A，这就证明了x∈B。
此外，我理解“由多项式时间算法决定的语言类别是多项式时间算法接受的语言类别的子集”。所以这个证明让我很困惑...
在计算复杂度理论中，P，也称为PTIME或 DTIME(n^O(1)) 是最基本的复杂性类别之一。它 包含可以通过确定性解决的所有决策问题 使用多项式计算时间的图灵机，或者 多项式时间。
来源：维基百科：P（复杂性）
不完全是。在这里，他想证明 A = B（接受 = 决定）。从定义上看，“决定”意味着机器总是在多项式时间内以正确答案“是”或“否”停止，而“接受”则意味着机器在多项式时间内以正确答案停止，当正确时答案是“是”；当正确答案为“否”时，它可以永远循环或回答“否”。显然第二个条件不太严格，因此很明显“决定”意味着“接受”，B包含在A中。因此证明主要是关于另一个方向，A包含在B中。这里他使用时间限制建造一台总是停止的机器。这种结构适用于所有有时间限制的类，前提是计数和限制时间停留的开销是类。
我不会假装回答，而是讨论它。其实我也需要答案！
我发现“在多项式时间内”非常令人不安： L 被 A 接受 ==> L 由 A 决定。
我会接受它作为概率，因为你需要指数时间才能知道它可以在多项式时间内被拒绝。但他们假装他们可以在 cn^k 时间内完成。所以我不明白模拟算法如何能够给出关于拒绝的确定答案。
这也意味着你不能有一个算法在多项式时间内接受 L 并在指数时间内拒绝它。也许在这里证明是一个更好的方法。 我对这个 P/NP 理论的问题是，我认为我已经理解了，但后来一切都崩溃了：我发现我还没有。