1
$\begingroup$

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?

Let me know your answer, please…

At the same time, if you want to see the details take a look in:

https://hal.archives-ouvertes.fr/hal-01490777v2/document

Thanks in advance…

$\endgroup$
  • 1
    $\begingroup$ Your question seems too broad/vague/open-ended to me. (Any community votes?) This site works best for focused, answerable technical questions; see our help center. It is not our goal here to make broad advances to science in a single post. See here for a related discussion. $\endgroup$ – D.W. Mar 22 '17 at 21:12

Your Answer

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

Browse other questions tagged or ask your own question.