It is possible to reduce EXACT COVER BY 3-SETS (X3C) problem, which is NP-Hard, to the SUBSET PRODUCT problem in polynomial time and show that the SUBSET PRODUCT problem is also NP-Hard.Kyle Jones shows this reduction in this link.I think that it is possible to reduce the SUBSET PRODUCT problem to the INTEGER FACTORIZATION problem and thus show that INTEGER FACTORIZATION problem is also NP-Hard by showing that polynomial solution to the INTEGER FACTORIZATION problem can be helpful to solve efficiently the SUBSET PRODUCT problem also in polynomial time.Remember that the SUBSET PRODUCT problem in general is:Show either$A \subset \mathbb{N} \land n \in \mathbb{N} \vdash \exists B: B \subseteq A \land \displaystyle \prod_{k \in B}k=n$OR$A \subset \mathbb{N} \land n \in \mathbb{N} \vdash \nexists B:B \subseteq A \land \displaystyle \prod_{k \in B}k=n$Of course that if an instance of the SUBSET PRODUCT problem is given, then the $A \subset \mathbb{N} \land n \in \mathbb{N}$ is replaced by $A=\{\ldots\} \land n=x$Where $\{\ldots\}\subset \mathbb{N} \land x \in \mathbb{N}$The SUBSET SUM problem in general is similar, and actually almost the same as the SUBSET PRODUCT problem, but with a little difference:Show either$A \subset \mathbb{N} \land n \in \mathbb{N} \vdash \exists B: B \subseteq A \land \displaystyle \sum_{k \in B}k=n$OR$A \subset \mathbb{N} \land n \in \mathbb{N} \vdash \nexists B: B \subseteq A \land \displaystyle \sum_{k \in B}k=n$Solution to the SUBSET PRODUCT problem by reducing it to the INTEGER FACTORIZATION problem:First of all remember that the INTEGER FACTORIZATION problem in general is:$n \in \mathbb{N} \land Factors(n) \subset PRIMES \land \displaystyle \prod_{k \in Factors(n)}k=n \vDash Factors(n)=?$If an instance of the INTEGER FACTORIZATION problem is given then $n \in \mathbb{N}$ is replaced by $n=x$ where $x \in \mathbb{N}$ and now it is needed to find out $?$, i.e. $Factors(x)$Let's assume that INTEGER FACTORIZATION $\in \mathbb{P}$ and let $GetFactors$ be a polynomial algorithm that returns all the factors of any natural number in polynomial time and so it solves the INTEGER FACTORIZATION problem in polynomial time.Now how the $GetFactors$ algorithm can be used to solve the SUBSET PRODUCT problem in polynomial time and show that $P=NP?$And the answer is that:$Factors(n) \subseteq A \vDash \exists B: B \subseteq A \land \displaystyle \prod_{k \in B}k=n$In that case $B=Factors(n)$$Factors(n) \nsubseteq A \land Factors(n) \subseteq \displaystyle \bigcup_{k \in A} Factors(k) \vDash \exists B: B \subseteq A \land \displaystyle \prod_{k \in B}=n$$Factors(n) \nsubseteq A \land Factors(n) \nsubseteq \displaystyle \bigcup_{k \in A} Factors(k) \vDash \nexists B: B \subseteq A \land \displaystyle \prod_{k \in B}=n$$\therefore \exists B: B \subseteq A \land \displaystyle \prod_{k \in B}k=n \equiv Factors(n) \subseteq A \lor Factors(n) \subseteq \displaystyle \bigcup_{k \in A} Factors(k)$ But I am unsure that this equivalent is true, but if it is true then:INTEGER FACTORIZATION $\in \mathbb{P} \implies$ SUBSET PRODUCT $\in \mathbb{P}$SUBSET PRODUCT $\in \mathbb{NP-HARD}$$\therefore$ INTEGER FACTORIZATION $\in \mathbb{NP-HARD}$Then is the equivalent above true?
Is integer factorization problem NP-Hard?
complexity theory