Return to Question

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?

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?

A candidate $\mathsf{NP}$ complete variant of factoring was posted in http://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?

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?

A candidate $\mathsf{NP}$ complete variant of factoring was posted in http://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 reduction to make the result effectively deterministic?

A candidate $\mathsf{NP}$ complete variant of factoring was posted in http://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?