NPクラスのこれらの問題はありますか?

$ { bf新規バージョン} $ [バージョン1.2]

$ mathbb {N} のすべての有限サブセットの集合を$ { bf Fin}( mathbb {Z})$とすると、
Z} $、$ W:{ bf Fin}( mathbb {Z})を mathbb {Z} $とすることができます。

For each $Ain {bf Fin}(mathbb{Z})$, let $n=|A|$,
$A={alpha_0, alpha_1, …, alpha_{n-1}}$, and
$m(A)=max{log_2{|alpha|}/ alpha in A}$. We use a sorting
algorithm in time $O(m n^2)$ to have $alpha_0 < alpha_1 <
…< alpha_{n-1}$, then encode every subset $Bsubseteq A$ by
the function $Encode_{A}: 2^A to mathbb{N}$,
$$Encode_{A}(B)=sumlimits_{0leq i<2^n$, and $Encode_{A}(B)$
can be computed in time $O(n^2)$.

それぞれのサブセット$ B subseteq S $に対して、$ S in { bf Fin}( mathbb
{Z})$を定義する $$ G_ {S、f}(B)=(1-W(B)) cdot f(Encode_ {S}(B))+ W

決定問題$ Prob_f $は以下のように定義される。


$ { bf問題} $ $ Prob_f $

INPUT: $Sin {bf Fin}(mathbb{Z})$.

QUESTION: Determine whether there exists a
subset $B$ of $S$ such that $G_{S, f}(B) = 0$?


私の質問は

  1. $ Prob_f $の問題は明確に定義されていますか?関数$ W $を明示的に定義する必要がありますか?

  2. $ O( log ^ k(n))$と$ W(A)$は時刻$ O(| A | ^ k)で計算可能であると仮定します。

  3. いくつかの一定の$ k $のための$。 $ Prob_f $は$ mathbf {NP} $ですか?


$ { bf古いバージョン} $

[バージョン1.1]

{0,1 } $を計算可能な関数とすると、$ mathbb {N}のすべての有限部分集合の集合を$ { bf
Fin}( mathbb {N} N} $、$ W:{ bf Fin}( mathbb {N})を {0,1 }
$と計算可能な関数とする。

{ bf Fin}( mathbb {N})$の各$ A について、 $ | A | $が$ Aの基数である$$
G_f(A)=(1 – W(A)) cdot f(| A |)+ W(A)決定問題$ Prob_f
$を以下のように定義する。


$ { bf問題} $ $ Prob_f $

INPUT: $Sin {bf Fin}(mathbb{N})$.

QUESTION: Determine whether there exists a
subset $B$ of $S$ such that $G_f(B) = 0$?


私の質問は

  1. $ Prob_f $の問題は明確に定義されていますか?関数$ W $を明示的に定義する必要がありますか?

  2. $ f(n)$は時間定数$ O( log ^ k(n))$でいくつかの定数$ k $で計算可能であると仮定し、$ W(A)$は$
    O(| A | ^ ell)$はいくつかの定数$ ell $です。 $ Prob_f $は$ mathbf {NP}
    $ですか?



[バージョン1.0] $ f: mathbb {N} を {0,1 } $を計算可能な関数とする。各有限集合$ S
$に対して、$ S_Sに依存する計算可能な関数$ W_S:2 ^ S 〜 {0,1 } $が与えられます。各部分集合$ A $
$ S $に対して、$$ F_ {S、f}(A)=(1-W_S(A)) cdot f(| A |)+ W_S(A)、$$ inこの$
A | $は$ Aの基数です。 決定問題$ Prob_f $を以下のように定義する。


$ { bf問題} $ $ Prob_f $

INPUT: A finite set $S$.

QUESTION: Determine whether there exists a
subset $B$ of $S$ such that $F_{S,f}(B) = 0$?

$ Prob_f $を解くアルゴリズムは、$ W_S
$をオラクルとみなし、決定する前にそれを呼び出すことに注意してください。


私の質問は

  1. $ Prob_f $の問題は明確に定義されていますか?関数$ W_S $を明示的に定義する必要がありますか?

  2. $ O( log ^ k(n))$で計算可能であると仮定します。 S | ^ ell)$をある一定の$ ell
    $に置き換えます。 $ Prob_f $は$ mathbf {NP} $ですか?

$ { bf注意} $。 $ W_S $は$ S $に依存する計算可能な関数であり、固定$ f $に対する問題$ Prob_f
$を考えるときに与えられる。たとえば、$ W_S(A)=(| A | + | S |) bmod 2 in
{0,1 } $で計算できます。 O( log_2(| S |)) subseteq O(| S |)$である。

私を助けてください!ありがとうございました。

ベストアンサー

更新された質問への回答(バージョン1.2):

この問題は、$ W $が事前に固定されている場合にのみ明確に定義されます。注意してほしいのは、問題は$ f $と$ W
$の両方に依存するので、$ Prob_ {f、W} $と呼ぶべきです。この問題の正確な複雑さは$ f $と$ W
$の両方に依存するかもしれません。

一度それをしたら、それはNPにあります。質問に対する答えが「はい」である場合、証明書はそのような集合$ B
$の一例である。この証明書は多項式のサイズを持ち、証明書は多項式時間で検証できます(仮定の下で)。したがって、NPに問題があります。それはNPの定義から直接得られます。特に、$
f、W $ごとに、$ Prob_ {f、W} $がNPにあることは真です。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です