# Is valid the notion of infinity for the NP-complete problems?

We have defined two complexity classes which have a close relation with the notion of infinity.

The first one is:

We say that a language $L$ belongs to $UP_{\infty}$ if there exist an infinite sequence of languages $L_{1}, L_{2}, L_{3} \ldots$ where for each $i \in \mathbb{N}$ every language $L_{i}$ is in $UP$, has an infinite cardinality, the set $L_{i + 1} – L_{i}$ has infinite elements and $L_{i} \subset L_{i + 1}$ such that $\lim_{i \rightarrow \infty} L_{i} = L.$ We call the complexity class $UP_{\infty}$ as $\textit{“infinite–UP”}$.

The second one:

We say that a language $L$ belongs to $P_{\infty}$ if there exist an infinite sequence of languages $L_{1}, L_{2}, L_{3} \ldots$ where for each $i \in \mathbb{N}$ every language $L_{i}$ is in $P$, has an infinite cardinality, the set $L_{i + 1} – L_{i}$ has infinite elements and $L_{i} \subset L_{i + 1}$ such that $\lim_{i \rightarrow \infty} L_{i} = L.$ We call the complexity class $P_{\infty}$ as $\textit{“infinite–P”}$.

We have the result:

We define a problem that we call General Quadratic Congruences. We show General Quadratic Congruences is an $\textit{NP–complete}$ problem. Moreover, we prove General Quadratic Congruences is also in $\textit{infinite–UP}$. In addition, we define another problem that we call Simple Subset Product. We show Simple Subset Product is an $\textit{NP–complete}$ problem. Furthermore, we prove Simple Subset Product is also in $\textit{infinite–P}$.

These problems are defined as follows:

$\textit{GENERAL QUADRATIC CONGRUENCES}$

INSTANCE: Positive integers $a$, $b$, $c$ and $d$, such that we have the prime factorization of $b$.

QUESTION: Is there a positive integer $x$ such that $x < c$ and $d \times x^{2} \equiv a (\mod b)$?

We denote this problem as $GQC$.

$\textit{SIMPLE SUBSET PRODUCT}$

INSTANCE: A list of numbers $L$ and a positive integer $k$ with its prime factorization, such that the prime factorization of $k$ does not contain any prime power with exponent greater than $1$.

QUESTION: Is there a subset of numbers from $L$ whose product is $k$?

We denote this problem as $SSP$.

MY QUESTION IS:

Can these properties of the NP-complete problems help us to understand better the P versus NP problem?