2
$\begingroup$

Say I have a number 45

What are the factors of 45?

1, 3, 5, 9, 15, 45

Is there any other factors?

I know that if I want to find some non trivial factor of some number, say 45, I know it's in NP.

I can non deterministically choose some 2 numbers and verify that those 2 numbers are factors of my large number. Verifying is easy. Just multiply the 2 numbers and see if it match.

What about if I want to find ALL factors of a large number? Is it still in NP?

How do we verify, in polynomial time, that 1, 3, 15, 45 are all the factors of 45? It turns out it isn't because we still have 5 and 9. But say someone says

Okay, 1, 3, 15, 45 are all factors of 45. How do we verify it in polynomial time?

Is it in NP?

Is it NP complete?

Does it has P verifier?

Basically, I wonder if the following problems are in NP

Say n is a number

Say S is a set of numbers between 1 and n

Is S the set of ALL factors of n or not.

A program should say it's false when

  1. One element of S, say s, is not a factor of n. We can verify this by dividing n by s and see if there are some reminders.
  2. There exist a number, say f, not in S, but is actually a factor of n.

Now is that problem NP?

$\endgroup$
2
  • $\begingroup$ Hint: What specific procedure would you use to do the "verify" step? Can you repeat this procedure? (Also: Why did you put "verify" in quotes?) $\endgroup$ May 20 '17 at 20:10
  • $\begingroup$ I wonder why I put it in quote? That's not NP problem. That's psychological problem. I removed the quote. He he he he... $\endgroup$
    – user4951
    May 20 '17 at 20:12
3
$\begingroup$

NP is a class of decision problems. Only decision problems can belong to NP. The problem "factor a number" is not a decision problem.

You can make up many decision problems that attempt to capture factoring. Here is one: the language of all quartets $(n,i,j,b)$ such that the $j$th bit of the $i$th prime factor of $n$ is equal to $b$. This language is in NP, since the factorization of $n$ functions as a witness (this uses the fact that primality can be tested in polynomial time; in fact, it is enough to know that primality is in NP, which is an easier fact). It is strongly suspected that this language is not NP-complete.

$\endgroup$
3
  • $\begingroup$ primality can be tested in polynomial time? How? $\endgroup$
    – user4951
    May 20 '17 at 20:16
  • 1
    $\begingroup$ Using the AKS primality test. $\endgroup$ May 20 '17 at 20:21
  • $\begingroup$ @JimThio: "primality is in NP" does not imply that primality can be tested in polynomial time. It can be tested in polynomial time, which is surprising, but "primality is in NP" does not imply this. $\endgroup$ May 20 '17 at 20:22

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.