4
$\begingroup$

A candidate $\mathsf{NP}$ complete variant of factoring was posted in https://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring, where decision problem $\text{BOUNDED-FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists n\in \{L, \ldots, U\})[n | N]\}$ was shown to be $\mathsf{NP}$ hard under randomized reductions under some results (http://plms.oxfordjournals.org/content/83/3/532) on prime numbers. A number theory question was posted in Are there effective small intervals in which primes are dense? whose answer provides a slightly different reduction from a bound of different nature on prime numbers.

Is there a different technique to remove randomness without any unknown conjectures and make the reduction deterministic?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ That post of mine and the answer to it together are enough to make the reduction effective (in the mathematical sense). $\;$ $\endgroup$
    – user5810
    Commented Aug 2, 2015 at 4:50
  • $\begingroup$ Are you using "effectively" in the informal sense? $\:$ If yes, then Cramér's conjecture is makes version #4 of Shor's answer "effectively deterministic". $\:$ If no, what does "effectively deterministic" mean? $\;\;\;\;$ $\endgroup$
    – user5810
    Commented Aug 3, 2015 at 13:36
  • $\begingroup$ @RickyDemer what does effective mean here concretely? $\endgroup$
    – Turbo
    Commented May 20, 2017 at 9:25
  • 1
    $\begingroup$ In this case, it means the proof allows construction of a specific algorithm and polynomial runtime-bound, rather than just showing that such exist. ​ ​ $\endgroup$
    – user5810
    Commented May 21, 2017 at 7:13

0

Reset to default

You must log in to answer this question.