My question will directly refer to the P vs NP Conjecture. It asks whether every problem whose solution can be quickly verified can also be solved quickly.
With the aid AKS primality testing we can organize primality testings in some polynomial time. For our main concerns we have the following
CONJECTURE
For $2n=a+b$, $n\in{N}>1$, consider all the possible expressions of the form $h_t(k) = ak + b^2$ with $gcd(a,b) =1$. Then there always exists minimum one $j$ for any choice of $i$ such that $h_i(c) = h_j(c) = P$, $i \neq j$, $a, b, c, i, j, k, t \in{N}$ and $P$ is any Prime Number respectively.
Illustration Consider $n =4$, then all such expressions are $h_1(k) = k+49$, $h_2(k) = 3k+25$, $h_3(k) = 7k+1$ and $h_4(k) = 5k+9$.
Now according to Conjecture we have $h_3(4) = h_4(4) = 29$ , $h_3(6) = h_2(6) = 43$ , $h_1(10) = h_4(10) = 59$ and $h_1(12) = h_2(12) = 61$
Source : Common Input yields Common Prime
Given any pair of such linear expression we could easily get the value of $k$ and consequentially the number which came as output has to be tested for primality.
As we introduce bigger even numbers to the system, the number of such linear expressions along with the output increases.
My question is- For significantly larger values of $n$
Is it hard to solve and easy to check? Or
Easy to solve and easy to check? Or
Hard to solve and hard to check?
By solving I meant that for any given $n$ we would obtain every such linear expression and would check the validity of Conjecture. Meanwhile checking is when we at random obtain the output and it's proven prime.
