Timeline for Number of divisors of a number - in NP?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 15, 2018 at 10:48 | answer | added | gnasher729 | timeline score: 1 | |
| Dec 15, 2018 at 10:13 | comment | added | Yuval Filmus | It is in NP. You’re confusing the value of a number with how many digits are required to represent it. | |
| Dec 15, 2018 at 10:12 | comment | added | caffein | So the problem is not in NP i understand ? the original problem ? | |
| Dec 15, 2018 at 10:12 | comment | added | Yuval Filmus | Unfortunately I cannot solve your exercise for you. | |
| Dec 15, 2018 at 10:12 | comment | added | caffein | Lets assume i proved the above. Now i have a certificate which is the factorization if my number m. I need to run x steps in order to check that the certificate is not too long. How many steps would that be ? | |
| Dec 15, 2018 at 10:12 | comment | added | Yuval Filmus | Indeed, it’s false. But it has $O(m)$ prime factors, which is quite easy to prove. | |
| Dec 15, 2018 at 10:10 | comment | added | caffein | 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. | |
| Dec 15, 2018 at 10:02 | comment | added | Yuval Filmus | Take it as an exercise. Use $2^{\log m} = m$. | |
| Dec 15, 2018 at 10:02 | comment | added | caffein | @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 | |
| Dec 15, 2018 at 10:00 | comment | added | caffein | @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... ? | |
| Dec 15, 2018 at 9:52 | comment | added | Yuval Filmus | 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. | |
| Dec 15, 2018 at 9:34 | history | asked | caffein | CC BY-SA 4.0 |