Note for the Millennium Prize Problems

EasyChair Preprint no. 11927, version 5

Versions: 12345678910history
11 pagesDate: February 6, 2024

Abstract

The Riemann hypothesis and the $P$ versus $NP$ problem are two of the most important unsolved Millennium Prize Problems. Let $\Psi(n) = n \cdot \prod_{q \mid n} \left(1 + \frac{1}{q} \right)$ denote the Dedekind $\Psi$ function where $q \mid n$ means the prime $q$ divides $n$. Define, for $n \geq 3$; the ratio $R(n) = \frac{\Psi(n)}{n \cdot \log \log n}$ where $\log$ is the natural logarithm. Let $N_{n} = 2 \cdot \ldots \cdot q_{n}$ be the primorial of order $n$. We prove if the inequality $R(N_{n+1}) < R(N_{n})$ holds for all primes $q_{n}$ (greater than some threshold), then the Riemann hypothesis is true. In this note, we show that the previous inequality always holds for all large enough prime numbers. $P$ versus $NP$ is considered as one of the most fundamental open problems in computer science. This consists in knowing the answer of the following question: Is $P$ equal to $NP$? It was essentially mentioned in 1955 from a letter written by John Nash to the United States National Security Agency. However, a precise statement of the $P$ versus $NP$ problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. Another major complexity class is $NP$-complete. It is well-known that $P$ is equal to $NP$ under the assumption of the existence of a polynomial time algorithm for some $NP$-complete. We show that the Monotone Weighted Xor 2-satisfiability problem ($MWX2SAT$) is $NP$-complete and $P$ at the same time.

Keyphrases: complexity classes, computational complexity, elementary number theory, polynomial time, prime numbers, Riemann hypothesis