我在复杂性证明方面遇到了一些困难：我处理了 3 个问题：A、B 和 C 我知道：
- A-> B
- A-> C
- C -> B
A-> B 含义：如果我对 A 有一个“是的答案”，那么我对 B 有一个“是的答案”。我知道 A 属于 NP，B 和 C 是 NP 完全的。此外，我可以为 A 编写一个对 C 进行二次调用的算法。
我可以推断出 A 的复杂性吗？
更准确地说：我有一个由 k 个对象组成的集合 P。如果所有这些对象都被移除，问题 A 的回答是，否则为否。如果这些对象之一可以被移除，则问题 C 的回答是，否则为否。我们有一个约束，即每一步都必须删除至少一个对象。在最坏的情况下，我们会进行 P 步。所以算法 A ：
for( i = 0 ; i < k){
for each object p of P
{
if C(p,P)=true then
remove p of P}
}
return P = emptyset