<p>Answer to updated question (version 1.2):</p>

<p>The problem is only well-defined if $W$ is fixed in advance.  Notationally, you should be calling it $Prob_{f,W}$, as the problem depends on both $f$ and $W$.  The exact complexity of the problem might depend on both $f$ and $W$.</p>

<p>Once you do that, yes, it is in NP.  If the answer to the question is "YES", then a certificate is an example of such a set $B$.  This certificate has polynomial size, and the certificate can be verified in polynomial time (under your assumptions).  Therefore, the problem is in NP.  It follows directly from the definition of NP.  In particular, for each $f,W$, it is true that $Prob_{f,W}$ is in NP.</p>

CC BY-SA 4.0
2018-05-31T18:17:15.873Z
@TDThu, the question still doesn't state whether $W_S$ is part of the input (an encoding of $W_S$ is provided as one of the inputs to the algorithm, and the algorithm has to work for all $W_S$); fixed (so the algorithm only has to work for a single $W_S$); or an oracle (the algorithm has to work for all $W_S$ but it isn't provided as input; rather there's an oracle which lets you compute $W_S$ in $O(1)$ time).  So, my comments and answer still stand.  I don't know what "given in specific" means.
D.W.
CC BY-SA 4.0
2018-06-01T01:17:54.123Z
@TDThu, uh-oh.  Please don't post new questions in the 'Your Answer' box.  See, e.g., https://cstheory.stackexchange.com/help/deleted-answers and https://meta.stackexchange.com/a/118597/160917.  Follow-up questions can potentially be posted as a new question using the 'Ask Question' button, but make sure to make them self-contained and follow the advice in our [help/on-topic].  I still don't understand what the phrase "given in specific" means, and adding "when we consider.." doesn't help me understand.
D.W.
CC BY-SA 4.0
2018-06-01T18:17:54.240Z
@TDThu, see updated answer.
D.W.
CC BY-SA 4.0
2018-06-02T05:16:37.583Z
@TDThu, I've edited my answer to answer your updated question.  I hope this will now answer your question and no further updates will be needed.
D.W.
CC BY-SA 4.0
2018-05-31T15:12:56.373Z
2018-06-02T05:16:11.653Z
2018-06-02T05:16:11.653Z
D.W.
<p>$Prob_f$ is not well-defined if $W_S$ is given as input. Therefore, I suggest viewing $W_S$ as a measure on the input set $S$ and is independent of $Prob_f$. What remains to be concerned is whether it is dependent of $S$. You should consider the following two cases:</p>

<ol>
<li><p>The definition of $W_S$ is not given and an algorithm $A$ solving $Prob_f$ will treat $W_S$ as an oracle, i.e., for each $U \subseteq S$, it must invoke $W_S$ to get $W_S(U) \in \{0,1\}$. Under the assumption that the computation of $W_S$ and the number of times $A$ invokes $W_S$ are in $O(|S|^k)$, I suppose that $Prob_f$ is in $\mathbf{NP}$.</p></li>
<li><p>The definition of $W_S$ is given and dependent of the input set $S$. In your last comment, you defined $W_S$ as the RSA-function that takes value in $\{0,1\}$: $W_S(A) = ((|A|+|S|)^D \bmod pq) \bmod 2)$. If $|p|,|q|,|D| \in O(|S|^k)$, I suppose that $Prob_f$ is in $\mathbf{NP}$. If $|p|,|q|,|D|$ are constants, $Prob_f$ definitely is in $\mathbf{P}$.</p></li>
</ol>

<p>(Note that $k$ is some constant and $|a|$ denotes the number of bits to represent $a$.)</p>

CC BY-SA 4.0
2018-05-29T05:47:02.817Z
Thank you so much for answer. Please give us a concrete example of $|p|,\ |q|\ , \ |D| \in O(|S|^k)$. Notice that $p,\ q,\ D$ must be defined uniquely for each finite subset $S$. Do you use $|x|$ for the size in bit-length of $x$? It is $log_2(x)$ for positive integer $x$...
TDThu
CC BY-SA 4.0
2018-05-29T07:29:23.007Z
Yes, I do. To be concrete, you can assume that $p$ is the greatest prime $\leq |S|$, $q$ is the greatest prime $\leq |S|^3$, and $D$ is an element of $\mathbb{Z}/(p-1)(q-1)\mathbb{Z}$ such that $\gcd((p-1)(q-1), D) = 1$ and $D$ is maximum in $\{1, 2, \dots, \lfloor\sqrt{pq}\rfloor\}$. By this definition, each $|S|$ will uniquely correspond to a tuple $(p,q,D)$. Note that $p$ and $q$ can be found deterministically in time $O(|S|^k)$ by the AKS algorithm.
Khoa Tran
CC BY-SA 4.0
2018-05-29T04:56:52.593Z
2018-05-29T06:41:09.523Z
2018-05-29T06:41:09.523Z
Khoa Tran
<p>${\bf New\ version}$ [Version 1.2]</p>

<p>Let $f: \mathbb{N} \to \{0,1\}$ be a computable function, ${\bf Fin}(\mathbb{Z})$ be the set of all finite subsets of $\mathbb{Z}$, and $W: {\bf Fin}(\mathbb{Z}) \to \mathbb{Z}$ be a computable function. </p>

<p>For each $A\in {\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 &lt; \alpha_1 &lt; ...&lt; \alpha_{n-1}$, then encode every subset $B\subseteq A$ by the function $Encode_{A}: 2^A \to \mathbb{N}$, 
$$Encode_{A}(B)=\sum\limits_{0\leq i&lt;n,\ \alpha_i \in B}2^i.$$ Notice that $0\leq Encode_{A}(B)&lt;2^n$, and $Encode_{A}(B)$ can be computed in time $O(n^2)$.</p>

<p>Let $S\in {\bf Fin}(\mathbb{Z})$, for each subset $B\subseteq S$, we define 
$$G_{S,f}(B) = (1 - W(B)) \cdot f(Encode_{S}(B)) + W(B).$$ </p>

<p>The decision problem $Prob_f$ is defined as follows.</p>

<hr>

<p>${\bf PROBLEM}$ $Prob_f$</p>

<p><strong>INPUT</strong>: $S\in {\bf Fin}(\mathbb{Z})$.</p>

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

<hr>

<p>My questions are</p>

<ol>
<li><p>Is the problem $Prob_f$ well-defined? Do we have to give an explicit definition of the function $W$?</p></li>
<li><p>Assume that $f(n)$ is computable in time $O(\log^k(n))$ and $W(A)$ is computable in time $O(|A|^k)$ for some constant $k$. Is $Prob_f$ in $\mathbf{NP}$?</p></li>
</ol>

<hr>

<hr>

<p>${\bf Old\ versions}$</p>

<p>[Version 1.1]</p>

<p>Let $f: \mathbb{N} \to \{0,1\}$ be a computable function, ${\bf Fin}(\mathbb{N})$ be the set of all finite subsets of $\mathbb{N}$, and $W: {\bf Fin}(\mathbb{N}) \to \{0,1\}$ be a computable function. </p>

<p>For each $A\in {\bf Fin}(\mathbb{N})$, we define 
$$G_f(A) = (1 - W(A)) \cdot f(|A|) + W(A),$$ in which $|A|$ is the cardinality of $A$. We define a decision problem $Prob_f$ as follows.</p>

<hr>

<p>${\bf PROBLEM}$ $Prob_f$</p>

<p><strong>INPUT</strong>: $S\in {\bf Fin}(\mathbb{N})$.</p>

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

<hr>

<p>My questions are</p>

<ol>
<li><p>Is the problem $Prob_f$ well-defined? Do we have to give an explicit definition of the function $W$?</p></li>
<li><p>Assume that $f(n)$ is computable in time $O(\log^k(n))$ for some constant $k$ and $W(A)$ is computable in $O(|A|^\ell)$ for some constant $\ell$. Is $Prob_f$ in $\mathbf{NP}$?</p></li>
</ol>

<hr>

<hr>

<p>[ Version 1.0 ]
Let $f: \mathbb{N} \to \{0,1\}$ be a computable function. For each finite set $S$, we are given a computable function $W_S: 2^S \to \{0, 1\}$, which depends on $S$. For each subset $A$ of $S$, we define $$F_{S,f}(A) = (1 - W_S(A)) \cdot f(|A|) + W_S(A),$$ in which $|A|$ is the cardinality of $A$. 
We define a decision problem $Prob_f$ as follows.</p>

<hr>

<p>${\bf PROBLEM}$ $Prob_f$</p>

<p><strong>INPUT</strong>: A finite set $S$.</p>

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

<p>Note that an algorithm for solving $Prob_f$ will regard $W_S$ as an oracle and invoke it before making a decision.</p>

<hr>

<p>My questions are</p>

<ol>
<li><p>Is the problem $Prob_f$ well-defined? Do we have to give an explicit definition of the function $W_S$?</p></li>
<li><p>Assume that $f(n)$ is computable in time $O(\log^k(n))$ for some constant $k$ and $W_S(A)$ is computable in $O(|S|^\ell)$ for some constant $\ell$. Is $Prob_f$ in $\mathbf{NP}$?</p></li>
</ol>

<p>${\bf Notes}$. $W_S$ is a computable function depending on $S$, which will be given in specific when we consider a problem $Prob_f$ for a fixed $f$. For example, $W_S(A)=(|A|+|S|)\ \bmod\ 2\ \in \{0,1\}$, which can be computed in time $\log_2(|A|)\in O(\log_2(|S|)) \subseteq O(|S|)$.</p>

<p>Please help me! Thank you.</p>

CC BY-SA 4.0
2018-05-27T16:32:56.263Z
I think that W_Sf(B) = 0 can be verified in polynomial time, it seems obvious. But I am not sure is it correct...
TDThu
CC BY-SA 4.0
2018-05-28T05:35:27.213Z
How is $W_S$ specified / provided as input?  Listing a truth table for $W_S$ takes exponential space, rendering the problem trivial.  If $W_S$ is an input, question 2 makes no sense (you can't assume that $W_S$ is computable in a certain amount of time as it is an input and someone might provide an input that doesn't satisfy that assumption).  If $W_S$ isn't an input, what exactly is the problem specification?  What are the inputs, and what is the desired output?  In that case it seems there are no inputs so the problem has a trivial algorithm (hardcode the answer in the algorithm).
D.W.
CC BY-SA 4.0
2018-05-28T05:38:16.890Z
$F_{S,f}(B)=0$ happens iff $W_S(B)=0$ and $f(|B|)=0$.  So a natural strategy for the problem is: for each $k \in \{0,1,\dots,|S|\}$, check whether $f(k)=0$ and if so check whether there exists $B \subseteq S$ such that $|B|=k$ and $W_S(B)=0$.  Whether this can be done efficiently depends on $W_S$ and how it is specified / provided as input.
D.W.
CC BY-SA 4.0
2018-05-28T10:41:55.907Z
${\bf Another\ example}$. Let $p$,$q$ be distinct primes, and let $D$ be a secret key in the RSA cryptosystem. $W_S(A)=((|A|+|S|)^D \bmod pq) \bmod 2$.
TDThu
CC BY-SA 4.0
2018-05-30T16:17:39.400Z
Please don't just leave clarifications in the comments.  Instead, edit the question so it reads well for people who encounter it for the first time, and to correct errors and improve the presentation.  We want people to be able to understand the question without having to read the comments, and for this to be useful for others too.
D.W.
CC BY-SA 4.0
2018-06-03T02:39:15.843Z
Please don't vandalize your question by deleting its contents.  Part of our mission is to build up a database of good questions and answers that might be useful to others in the future.  Defacing your question by removing the content is impolite to answerers who have taken the time to write an answer to your question.
D.W.
<computability><np><complexity>
Are these problems in NP class?
TDThu
# Are these problems in NP class?

(Asked by: username_0 on 2018-05-27)

${\bf New\ version}$ [Version 1.2]

Let $f: \mathbb{N} \to \{0,1\}$ be a computable function, ${\bf Fin}(\mathbb{Z})$ be the set of all finite subsets of $\mathbb{Z}$, and $W: {\bf Fin}(\mathbb{Z}) \to \mathbb{Z}$ be a computable function.

For each $A\in {\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 $B\subseteq A$ by the function $Encode\_{A}: 2^A \to \mathbb{N}$,
$$Encode\_{A}(B)=\sum\limits\_{0\leq i

Let $S\in {\bf Fin}(\mathbb{Z})$, for each subset $B\subseteq S$, we define
$$G\_{S,f}(B) = (1 - W(B)) \cdot f(Encode\_{S}(B)) + W(B).$$

The decision problem $Prob\_f$ is defined as follows.

---

${\bf PROBLEM}$ $Prob\_f$

**INPUT**: $S\in {\bf Fin}(\mathbb{Z})$.

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

---

My questions are

1. Is the problem $Prob\_f$ well-defined? Do we have to give an explicit definition of the function $W$?
2. Assume that $f(n)$ is computable in time $O(\log^k(n))$ and $W(A)$ is computable in time $O(|A|^k)$ for some constant $k$. Is $Prob\_f$ in $\mathbf{NP}$?

---

---

${\bf Old\ versions}$

[Version 1.1]

Let $f: \mathbb{N} \to \{0,1\}$ be a computable function, ${\bf Fin}(\mathbb{N})$ be the set of all finite subsets of $\mathbb{N}$, and $W: {\bf Fin}(\mathbb{N}) \to \{0,1\}$ be a computable function.

For each $A\in {\bf Fin}(\mathbb{N})$, we define
$$G\_f(A) = (1 - W(A)) \cdot f(|A|) + W(A),$$ in which $|A|$ is the cardinality of $A$. We define a decision problem $Prob\_f$ as follows.

---

${\bf PROBLEM}$ $Prob\_f$

**INPUT**: $S\in {\bf Fin}(\mathbb{N})$.

**QUESTION**: Determine whether there exists a subset $B$ of $S$ such that $G\_f(B) = 0$?

---

My questions are

1. Is the problem $Prob\_f$ well-defined? Do we have to give an explicit definition of the function $W$?
2. Assume that $f(n)$ is computable in time $O(\log^k(n))$ for some constant $k$ and $W(A)$ is computable in $O(|A|^\ell)$ for some constant $\ell$. Is $Prob\_f$ in $\mathbf{NP}$?

---

---

[ Version 1.0 ]
Let $f: \mathbb{N} \to \{0,1\}$ be a computable function. For each finite set $S$, we are given a computable function $W\_S: 2^S \to \{0, 1\}$, which depends on $S$. For each subset $A$ of $S$, we define $$F\_{S,f}(A) = (1 - W\_S(A)) \cdot f(|A|) + W\_S(A),$$ in which $|A|$ is the cardinality of $A$.
We define a decision problem $Prob\_f$ as follows.

---

${\bf PROBLEM}$ $Prob\_f$

**INPUT**: A finite set $S$.

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

Note that an algorithm for solving $Prob\_f$ will regard $W\_S$ as an oracle and invoke it before making a decision.

---

My questions are

1. Is the problem $Prob\_f$ well-defined? Do we have to give an explicit definition of the function $W\_S$?
2. Assume that $f(n)$ is computable in time $O(\log^k(n))$ for some constant $k$ and $W\_S(A)$ is computable in $O(|S|^\ell)$ for some constant $\ell$. Is $Prob\_f$ in $\mathbf{NP}$?

${\bf Notes}$. $W\_S$ is a computable function depending on $S$, which will be given in specific when we consider a problem $Prob\_f$ for a fixed $f$. For example, $W\_S(A)=(|A|+|S|)\ \bmod\ 2\ \in \{0,1\}$, which can be computed in time $\log\_2(|A|)\in O(\log\_2(|S|)) \subseteq O(|S|)$.

Please help me! Thank you.

**Tags:** computability, np, complexity

> **Comments:**
> **username_0**: I think that W_Sf(B) = 0 can be verified in polynomial time, it seems obvious. But I am not sure is it correct...  
> **username_1**: How is $W_S$ specified / provided as input?  Listing a truth table for $W_S$ takes exponential space, rendering the problem trivial.  If $W_S$ is an input, question 2 makes no sense (you can't assume that $W_S$ is computable in a certain amount of time as it is an input and someone might provide an input that doesn't satisfy that assumption).  If $W_S$ isn't an input, what exactly is the problem specification?  What are the inputs, and what is the desired output?  In that case it seems there are no inputs so the problem has a trivial algorithm (hardcode the answer in the algorithm).  
> **username_1**: $F_{S,f}(B)=0$ happens iff $W_S(B)=0$ and $f(|B|)=0$.  So a natural strategy for the problem is: for each $k \in \{0,1,\dots,|S|\}$, check whether $f(k)=0$ and if so check whether there exists $B \subseteq S$ such that $|B|=k$ and $W_S(B)=0$.  Whether this can be done efficiently depends on $W_S$ and how it is specified / provided as input.  
> **username_0**: ${\bf Another\ example}$. Let $p$,$q$ be distinct primes, and let $D$ be a secret key in the RSA cryptosystem. $W_S(A)=((|A|+|S|)^D \bmod pq) \bmod 2$.  
> **username_1**: Please don't just leave clarifications in the comments.  Instead, edit the question so it reads well for people who encounter it for the first time, and to correct errors and improve the presentation.  We want people to be able to understand the question without having to read the comments, and for this to be useful for others too.  
> **username_1**: Please don't vandalize your question by deleting its contents.  Part of our mission is to build up a database of good questions and answers that might be useful to others in the future.  Defacing your question by removing the content is impolite to answerers who have taken the time to write an answer to your question.  

---

## 2 answers

### Answer by username_1 on 2018-05-31. Score: 1

Answer to updated question (version 1.2):

The problem is only well-defined if $W$ is fixed in advance. Notationally, you should be calling it $Prob\_{f,W}$, as the problem depends on both $f$ and $W$. The exact complexity of the problem might depend on both $f$ and $W$.

Once you do that, yes, it is in NP. If the answer to the question is "YES", then a certificate is an example of such a set $B$. This certificate has polynomial size, and the certificate can be verified in polynomial time (under your assumptions). Therefore, the problem is in NP. It follows directly from the definition of NP. In particular, for each $f,W$, it is true that $Prob\_{f,W}$ is in NP.

> **Comments:**
> **username_1**: @username_0, the question still doesn't state whether $W_S$ is part of the input (an encoding of $W_S$ is provided as one of the inputs to the algorithm, and the algorithm has to work for all $W_S$); fixed (so the algorithm only has to work for a single $W_S$); or an oracle (the algorithm has to work for all $W_S$ but it isn't provided as input; rather there's an oracle which lets you compute $W_S$ in $O(1)$ time).  So, my comments and answer still stand.  I don't know what "given in specific" means.  
> **username_1**: @username_0, uh-oh.  Please don't post new questions in the 'Your Answer' box.  See, e.g., https://cstheory.stackexchange.com/help/deleted-answers and https://meta.stackexchange.com/a/118597/160917.  Follow-up questions can potentially be posted as a new question using the 'Ask Question' button, but make sure to make them self-contained and follow the advice in our [help/on-topic].  I still don't understand what the phrase "given in specific" means, and adding "when we consider.." doesn't help me understand.  
> **username_1**: @username_0, see updated answer.  
> **username_1**: @username_0, I've edited my answer to answer your updated question.  I hope this will now answer your question and no further updates will be needed.  

---

### Answer by username_2 on 2018-05-29. Score: 1

$Prob\_f$ is not well-defined if $W\_S$ is given as input. Therefore, I suggest viewing $W\_S$ as a measure on the input set $S$ and is independent of $Prob\_f$. What remains to be concerned is whether it is dependent of $S$. You should consider the following two cases:

1. The definition of $W\_S$ is not given and an algorithm $A$ solving $Prob\_f$ will treat $W\_S$ as an oracle, i.e., for each $U \subseteq S$, it must invoke $W\_S$ to get $W\_S(U) \in \{0,1\}$. Under the assumption that the computation of $W\_S$ and the number of times $A$ invokes $W\_S$ are in $O(|S|^k)$, I suppose that $Prob\_f$ is in $\mathbf{NP}$.
2. The definition of $W\_S$ is given and dependent of the input set $S$. In your last comment, you defined $W\_S$ as the RSA-function that takes value in $\{0,1\}$: $W\_S(A) = ((|A|+|S|)^D \bmod pq) \bmod 2)$. If $|p|,|q|,|D| \in O(|S|^k)$, I suppose that $Prob\_f$ is in $\mathbf{NP}$. If $|p|,|q|,|D|$ are constants, $Prob\_f$ definitely is in $\mathbf{P}$.

(Note that $k$ is some constant and $|a|$ denotes the number of bits to represent $a$.)

> **Comments:**
> **username_0**: Thank you so much for answer. Please give us a concrete example of $|p|,\ |q|\ , \ |D| \in O(|S|^k)$. Notice that $p,\ q,\ D$ must be defined uniquely for each finite subset $S$. Do you use $|x|$ for the size in bit-length of $x$? It is $log_2(x)$ for positive integer $x$...  
> **username_2**: Yes, I do. To be concrete, you can assume that $p$ is the greatest prime $\leq |S|$, $q$ is the greatest prime $\leq |S|^3$, and $D$ is an element of $\mathbb{Z}/(p-1)(q-1)\mathbb{Z}$ such that $\gcd((p-1)(q-1), D) = 1$ and $D$ is maximum in $\{1, 2, \dots, \lfloor\sqrt{pq}\rfloor\}$. By this definition, each $|S|$ will uniquely correspond to a tuple $(p,q,D)$. Note that $p$ and $q$ can be found deterministically in time $O(|S|^k)$ by the AKS algorithm.  

---

