1
$\begingroup$

Knowing D={p|p is a polynomial evaluating to 0 for some assignment of integers to its variables} is not decidable, how can I prove that E={p|p is a polynomial evaluating to a prime for some assignment of integers to its variables} is not decidable?

Proving that D is mapping reducible or Turing reducible to E would be enough, since if D < E ( where < means mapping reducible), then E decidable => D decidable, and using the contrapositive we get D not decidable => E not decidable.

Is showing that D is mapping or Turing reducible to E the right approach? I don't see how it can be proved. Thanks!

$\endgroup$

1 Answer 1

2
$\begingroup$

Yes like you say, you have to show that an algorithm that solves $E$ can be used to solve $D$.

A practical approach is to give a polynomial $p_E$ for every polynomial $p$ such that $p$ evaluates to $0$ iff $p_E$ evaluates to a prime number.

$\endgroup$
4
  • $\begingroup$ Would something like "On input p: If p can be evaluated to 0, output polynomial y-6. Else output polynomial 6" work? This is essentially a TM that computes a function f such that f(x) is in E if and only if x is in D. $\endgroup$
    – John
    Commented Nov 27, 2016 at 3:17
  • 1
    $\begingroup$ No, that will not work, because you first have to solve the problem itself before you assign the polynomial. Hint if $p$ is a polynomial then polynomial $2p$ will not evaluate to a prime unless under specific conditions. $\endgroup$ Commented Nov 27, 2016 at 12:34
  • $\begingroup$ I am still having trouble understanding how to proceed, is your approach used for a mapping reduction or a Turing reduction? Given a polynomial p that evaluates to prime n, then (p-n) evaluates to 0. And as you said, 2p does not evaluate to a prime. I can compute a reduction from E to D using the former fact, but how can it be used in computing a reduction from D to E? Thanks! $\endgroup$
    – John
    Commented Nov 28, 2016 at 2:17
  • $\begingroup$ More precisely: $2p$ evaluates to a prime iff $p$ evaluates to $1$. (Ignoring negative thingies.) This ties "evaluating to a prime" to "evaluating to a specific value". $\endgroup$ Commented Nov 28, 2016 at 2:22

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.