1

私は複雑さの証明にいくつかの困難があります:私は3つの問題を扱っています:A、B、C私は知っています:

  • A-> B
  • A-> C
  • C -> B

A-> B 意味: A に対して「はい」の答えがある場合、B に対して「はい」の答えがあります。A が NP に属し、B と C が NP 完全であることを知っています。さらに、C への 2 次数の呼び出しを使用して A のアルゴリズムを作成できます
。A の複雑さについて何か推測できますか?

より正確に言うと、k 個のオブジェクトのセット P があります。問題 A は、これらのオブジェクトがすべて削除された場合は「はい」と答え、それ以外の場合は「いいえ」と答えます。問題 C は、これらのオブジェクトの 1 つを削除できる場合は「はい」と答え、それ以外の場合は「いいえ」と答えます。各ステップで少なくとも 1 つのオブジェクトを削除する必要があるという制約があります。最悪の場合、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
4

1 に答える 1

0

B -> A とは述べていないので、A は自明なケースまたは多項式時間で決定できるケースでのみ yes の回答を必要とする場合がありますが、B の回答を決定するには、より複雑なケースが必要になるため、より多くの時間が必要になります。はい答えます。あなたの質問に対する短い答え：いいえ。

于 2015-04-08T10:13:16.333 に答える