-1
$\begingroup$

${\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<n,\ \alpha_i \in B}2^i.$$ Notice that $0\leq Encode_{A}(B)<2^n$, and $Encode_{A}(B)$ can be computed in time $O(n^2)$.

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.

$\endgroup$
  • $\begingroup$ I think that W_Sf(B) = 0 can be verified in polynomial time, it seems obvious. But I am not sure is it correct... $\endgroup$ – TDThu May 27 '18 at 16:32
  • 2
    $\begingroup$ 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). $\endgroup$ – D.W. May 28 '18 at 5:35
  • 1
    $\begingroup$ $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. $\endgroup$ – D.W. May 28 '18 at 5:38
  • $\begingroup$ ${\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$. $\endgroup$ – TDThu May 28 '18 at 10:41
  • 2
    $\begingroup$ 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. $\endgroup$ – D.W. May 30 '18 at 16:17
1
$\begingroup$

$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$.)

$\endgroup$
  • $\begingroup$ 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$... $\endgroup$ – TDThu May 29 '18 at 5:47
  • $\begingroup$ 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. $\endgroup$ – Khoa Tran May 29 '18 at 7:29
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – D.W. May 31 '18 at 18:17
  • $\begingroup$ @TDThu, uh-oh. Please don't post new questions in the 'Your Answer' box. See, e.g., cstheory.stackexchange.com/help/deleted-answers and 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 center. I still don't understand what the phrase "given in specific" means, and adding "when we consider.." doesn't help me understand. $\endgroup$ – D.W. Jun 1 '18 at 1:17
  • $\begingroup$ @TDThu, see updated answer. $\endgroup$ – D.W. Jun 1 '18 at 18:17
  • $\begingroup$ @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. $\endgroup$ – D.W. Jun 2 '18 at 5:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.