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.

Improve this question
$\endgroup$
9
  • $\begingroup$ I'm not quite clear on this. Could you give an example of an odd perfect number? $\endgroup$
    – gnasher729
    Commented Feb 3, 2018 at 15:39
  • 2
    $\begingroup$ And what makes you think this is NP hard? $\endgroup$
    – gnasher729
    Commented Feb 3, 2018 at 15:40
  • $\begingroup$ Oh, I'm quite sure it's in NP. Only don't know how to prove it. $\endgroup$
    – Anwar Saiah
    Commented Feb 3, 2018 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
    Commented Feb 3, 2018 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
    Commented Feb 3, 2018 at 17:51

1 Answer 1

Reset to default
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...)

Improve this answer
$\endgroup$
8
  • $\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
    Commented Feb 4, 2018 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
    Commented Feb 4, 2018 at 8:13
  • 1
    $\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
    Commented Feb 4, 2018 at 9:56
  • 1
    $\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
    Commented Feb 4, 2018 at 9:59
  • 1
    $\begingroup$ Given a factorization of $n$ into primes, you can easily verify that it is perfect. $\endgroup$
    – Yuval Filmus
    Commented Jun 9, 2021 at 10:05

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.