1
$\begingroup$

I'm trying to show that the language {(m,n)|m has exactly n divisors} is in NP.

The input (m,n) is in binary.

The non-deterministic Turing machine for the language would be:

1) Guess the prime factors of m.

2) Verify that ∏i(di+1)=n.

The problem is that I can't find a way to factorize in polynomial time (in the input) the number m.

If stage 1 takes m steps then it would be m=2 ^ log(m) and the whole algorithm would run in exponential time.

How can I prove that verifying that m has exactly n divisors is in NP ? Perhaps not via factorization but somehow else. I've run out of ideas.

Improve this question
$\endgroup$
10
  • $\begingroup$ You seem to be misunderstanding the difference between P and NP. An NP machine doesn’t have to compute a factorization in polytime - it just as to be able to verify a given factorization in polytime. To this end, it’s useful to know that primality testing is in P. $\endgroup$
    – Yuval Filmus
    Commented Dec 15, 2018 at 9:52
  • $\begingroup$ @YuvalFilmus I know that i can get a certificate and just verify it but what would it be ? If the certificate is the list of prime factors then i need to check if it is of length O(log(m)) but how long do i run to check its length - 2logm, 3 logm, 4logm... ? $\endgroup$
    – caffein
    Commented Dec 15, 2018 at 10:00
  • $\begingroup$ @YuvalFilmus Also, how do i prove that the number of prime factors of m is log(m) ? If it is longer then the whole machine would run in non polynomial time $\endgroup$
    – caffein
    Commented Dec 15, 2018 at 10:02
  • $\begingroup$ Take it as an exercise. Use $2^{\log m} = m$. $\endgroup$
    – Yuval Filmus
    Commented Dec 15, 2018 at 10:02
  • $\begingroup$ The problem is that i need a formal proof and after googling it doesn't seem trivial at all - to prove that a number with m digits has O(log(m)) prime factors. $\endgroup$
    – caffein
    Commented Dec 15, 2018 at 10:10

1 Answer 1

Reset to default
1
$\begingroup$

A number with k binary digits has at most k prime factors. That's because the smallest number with k prime factors is 2^k.

So given a number m with k binary digits you can easily be given a list of the prime factors of m. You can check that the product of these prime factors is indeed m in polynomial time easily. You can easily calculate the number of factors from the prime factors in polynomial time.

But what you also need to do is that the purported list of prime factors is actually a list of primes. Here comes another theorem that shows for every prime p, there is an easily verifiable proof that p is indeed a prime.

The oracle should contain a list of the prime factors, and for every item in the list an oracle for proving that it is prime.

For being in NP, there is absolutely no need that you are able to provide the oracle in polynomial time. You only need to be able to check it in polynomial time.

Improve this answer
$\endgroup$
1
  • $\begingroup$ We actually know today that you can determine whether an integer is prime in polynomial time. $\endgroup$
    – Yuval Filmus
    Commented Dec 15, 2018 at 19:06

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.