0
$\begingroup$

A perfect natural number is that which is equal to the sum of it's divisors. For example 6 is perfect: 1+2+3=6 also 28 is perfect.

Prove the following language is NP hard:

L={< n> | n is a perfect natural number}.

You can use the fact that if

$$n=p_{1}^{m_{1}}p_{2}^{m_{2}} \cdot \cdot \cdot p_{k}^{m_{k}}$$

where $p_{i}$ are n's prime divisors, then the sum of n's divisors including n would be:

$$(1+p_{1}+p_{1}^2+...+p_{1}^{m_{1}})(1+p_{2}+p_{2}^2+...+p_{2}^{m_{2}})\cdot \cdot \cdot (1+p_{k}+p_{k}^2+...+p_{k}^{m_{k}})$$ Now I know the proof should contain a polynomial time reduction from some NP problem to this language L, most likely from SAT, I only can't figure out how to go about it, any guidance would be appreciated.

$\endgroup$
  • $\begingroup$ I'm not quite clear on this. Could you give an example of an odd perfect number? $\endgroup$ – gnasher729 Feb 3 '18 at 15:39
  • 2
    $\begingroup$ And what makes you think this is NP hard? $\endgroup$ – gnasher729 Feb 3 '18 at 15:40
  • $\begingroup$ Oh, I'm quite sure it's in NP. Only don't know how to prove it. $\endgroup$ – Anwar Saiah Feb 3 '18 at 17:46
  • $\begingroup$ I thought about taking an input to SAT and manipulate it to be an input to this problem. Just don't have the right starting point yet. $\endgroup$ – Anwar Saiah Feb 3 '18 at 17:48
  • $\begingroup$ Oh and I can't find any odd number that is perfect! I don't think there exists one. $\endgroup$ – Anwar Saiah Feb 3 '18 at 17:51
1
$\begingroup$

NP ≠ NP hard.

NP means: For every perfect number, there is a certificate that lets you prove in polynomial time that it is perfect.

And that is clearly the case. For every perfect number, I can give you the factorisation, plus for all large prime factors a proof that these large factors are primes, and then you can quite easily check that the number is perfect.

NP hard means: If you can solve this problem, then you can solve any problem in NP. I don't see this. Especially since perfect numbers are so rare. (Why does it make it unlikely that this is NP hard? Polynomial time reduction means: If you take a problem in NP, then for any instance with answer "Yes" there is a perfect number so that the fact that this number is perfect proves the answer to your problem is "Yes". For different instances I'd expect different perfect numbers to be needed. But there are so few known...)

$\endgroup$
  • $\begingroup$ Great, right on the money. I've been struggling to show a reduction while non existed.You are absolutely right there, all I needed was a polynomial verifier.But there remains a question, why did they bother with the prime divisors?How is this easier than just giving the certificate as the divisors them selves!For example for 28 they suggest I use the prime factors of 28 (1+2+$2^2$)(1+7)=2*28 while I can simply give (1,2,4,7,14) as the certificate and the verifier would simply check if their sum is 28 ?? $\endgroup$ – Anwar Saiah Feb 4 '18 at 2:14
  • $\begingroup$ Ok, I will answer my last comment, this could be the case that you might send some divisors of the number that fit the description while the number is not perfect, some of the divisors do but not all. But I'm not fully sure of it yet. $\endgroup$ – Anwar Saiah Feb 4 '18 at 8:13
  • $\begingroup$ Assuming that there exist no odd perfect numbers, this language is actually in P, since an even number is perfect iff it is of the form $2^{p-1} (2^p-1)$, where $2^p-1$ is prime (recall primality checking is also in P). $\endgroup$ – Yuval Filmus Feb 4 '18 at 9:56
  • $\begingroup$ Answering your question about the witness, don't forget that it has to have polynomial size. This is easy to see when giving the entire factorization, and not necessarily true when giving a list of all divisors. Also, how would you check that these are indeed all divisors? $\endgroup$ – Yuval Filmus Feb 4 '18 at 9:59
  • $\begingroup$ @AnwarSaiah: If I give you a certificate including a large prime factor p, you don't actually know it's a prime. You have to check the factor. It can be that if p is prime then your number n is perfect, but if p is composite then n is not perfect. You can't just believe the certificate, you have to check it. $\endgroup$ – gnasher729 Feb 4 '18 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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