7
$\begingroup$

$\newcommand\NP{\mathit{NP}}\newcommand\SAT{\mathit{SAT}}\newcommand\CH{\mathit{CH}}\newcommand\PSPACE{\mathit{PSPACE}}$Are there $\NP$-hard problems which are $\NP$-complete under the Riemann Hypothesis corresponding to the following cases?

  1. Superpolynomial certificate length becomes polynomial sized.

  2. Randomized polynomial time reduction to $\SAT$ becomes deterministic polynomial time reduction.

  3. Reduction to $\SAT$ becomes polynomial deterministic time from superpolynomial deterministic time.

  4. Certificate becomes polynomial time verifiable.

  5. An infinitely often reduction always holds.

  6. The problem was originally in $\CH$ (counting hierarchy) or below and strictly in $\PSPACE$.

I think 2. and 6. are impossible unless RH is false and so might be difficult to identify while 1., 3. and 4. might be similar.

Bounty is for 2. or 6.

I would be happy to award for 2. and 6. if there is a reduction for these under the condition of failure of RH and in my opinion such a twisted reduction is allowed but just 2. and 6. are disallowed under correctness of RH.

It would be amazing if there are reductions to 2. and 6. under both truth and falseness of RH and this I think is unlikely since I think reduction under truth of RH is unlikely.

$\endgroup$
4
  • 2
    $\begingroup$ Not exactly what you want, but this paper sciencedirect.com/science/article/pii/S0885064X96900199 shows that Nullstellensatz is in a class "just above" NP if GRH is true. $\endgroup$ Aug 4, 2021 at 12:17
  • 2
    $\begingroup$ @BenjaminSteinberg Conjecturally, the class is indeed NP itself, making the problem NP-complete. That is, what Koiran proves is that assuming GRH, solvability of (integer) polynomial systems in $\mathbb C$ is computable in AM. (I’m not sure why he calls it “Nullstellensatz”, as the Nullstellensatz is a theorem, not a computational problem.) There are plausible complexity-theoretic conjectures that imply AM = NP. $\endgroup$ Aug 4, 2021 at 13:09
  • $\begingroup$ @BenjaminSteinberg I think it answers an analogous version of 1. and 3. $\endgroup$
    – Turbo
    Aug 5, 2021 at 22:11
  • $\begingroup$ @EmilJeřábek If the problem was unconditionally below PSPAPCE in Benjamin Steinberg's comment it would answer 6. $\endgroup$
    – Turbo
    Aug 7, 2021 at 19:25

1 Answer 1

3
$\begingroup$

Here's an example, but you may consider it to be a bit artificial Consider the following language: s is in $L$ if $S=(x,y)$ where $x$ is a 3-SAT instance, $y$ is a satisfying instance for $y$, and also satisfying that if $n$ is the number of true variables in $y$, then the $n$th non-trivial zero of the zeta function has real part equal to $1/2$. But this is a bit artificial. My guess is that you specified your five examples in order to avoid that.

Edit: The following does not work. Possibly it can be fixed, but see Emil's comment below.

But we can modify this is a little bit to cheat and get an example of 1, provided one is willing to use GRH rather than RH; my guess is that a similar construction can be done with RH, but it doesn't immediately jump out at me. The first detail is that assuming GRH, the smallest positive primitive root $u$, of a prime $p$ is bounded above by a power of $\log p$. In particular, Shoup showed that $u = O( (\log p)^6)$.

Given positive constants $c_1$, $c_2$, and a function $f(n)$ Let $A_{c_1,c_2, f(n)}$ be the language given by the following: $a$ is in $A$ if $a=(x,y,z,w)$ where $x$, $y$, and $z$ are defined as follows. We have $x$ is a 3-SAT instance and $y$ is a satisfying set of variables for $x$. $z$ is a prime $p$ such that $y< p < (c_1)p^{c_2}$ (where we are thinking of our list $y$ of variable assignments as just a binary number). We have $w$ is a string of 1s where the number of 1s is a primitive root of $p$, and $w$'s length is bounded by $f(p)$.

Now, we can choose a $c_1$ and $c_2$ such that there is always such a prime $p$ when there is a $y$. (Baker, Harman and Pintz showed that one can take $c_2 = 0.525$). So choose such a $c_1$ and $c_2$. Then, note that if we believe GRH, we can always find such a $w$ which is polynomial in the length of $x$, and we can choose $f(n)$ so that $w$'s length is guaranteed to be less than $f(p)$ if GRH is true.

So now our NP-hard question then is just is a given $x$ a valid $x$ for an $(x,y,z,w)$ in $A$? If GRH is true, we can always find a $y$, $z$ and $w$ which is guaranteed to be just polynomial in length when $x$ is true. But without GRH we can only get that this is NP-hard since our $w$ may be too large.

This is essentially just a padding trick. My guess is that a similar padding trick can be used with just RH as an assumption but I don't immediately see how to do it. And this is still a pretty artificial problem. I'd be interested to see if someone has a more natural example.

$\endgroup$
2
  • 1
    $\begingroup$ I cannot make sense of the example. As far as I can see, the language $\{x:\exists y,z,w\,(x,y,z,w)\in A\}$ is unconditionally in NP, because it equals $\{x:\exists y,z,w\,(x,y,z,w)\in A'\}$, where $A'$ is defined just like $A$, except that $w$ is written in binary rather than unary. (Actually, neither $A$ nor $A'$ is computable in polynomial-time, as verifying that something is a primitive root requires factorization of $p-1$. But this is not a problem, as the factorization of $p-1$ can be taken as part of the witness.) On the other hand, it’s not clear to me why is the language NP-hard. $\endgroup$ Aug 4, 2021 at 12:51
  • $\begingroup$ @EmilJeřábek You are correct. This doesn't work. I think some padding trick should be doable but my attempted answer has multiple problems. $\endgroup$
    – JoshuaZ
    Aug 4, 2021 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.