8
$\begingroup$

It is said that integer factorization is an NP problem.

Why isn't it P? You can solve it in $O(\sqrt{n})$ time with trial factorization, and since $\sqrt{n} = n^{1/2}$, to me that looks like a number of form $n^k$ which is a polynomial.

I am having difficulty determining what P vs NP vs NP-Complete vs NP-Hard means because I don't know how to separate the definitions and how complexity is measured and defined.

$\endgroup$
  • 6
    $\begingroup$ The size of the problem "factor the number $n$" is not $n$; it's the number of bits needed to represent $n$, i.e., the logarithm of $n$, which is much smaller. $\endgroup$ – bof Jan 24 '16 at 1:54
  • 1
    $\begingroup$ Solution in $O(\sqrt{n})$ time? Recall that $n$ here is the number of digits (or number of bits) in the number to be factored. $\endgroup$ – GEdgar Jan 24 '16 at 1:55
  • $\begingroup$ Why does that matter? For instance if I am finding the max of a list of $n$ numbers, it's done in $O(n)$ time because there are $n$ elements. Similarly, factoring an integer $n$ is done in $O(\sqrt{n})$ time because you can get the factors iterating up to its square root, in the same way you can check if a given number is prime, which I believe belongs to complexity class P. $\endgroup$ – Nakano Jan 24 '16 at 1:56
  • $\begingroup$ @Nakano In the case of the "maximum of list," it is done in $O(n)$ time because the size of the input is $n$ since the input has $n$ integers. However, in the factorization problem, the size of the input is $\log n$ since the input is just $n$ and is thus represented with $\log n$ bits. $\endgroup$ – Noble Mushtak Jan 24 '16 at 2:01
  • 1
    $\begingroup$ How would you represent $n$ integers with $\log n$ bits? You need at least one bit for each integer, which requires at least $n$ bits. $\endgroup$ – Noble Mushtak Jan 24 '16 at 2:11
4
$\begingroup$

Let $k$ denote the length of the input value $n$.

Since $k=\log_2n$, a complexity of $O(\sqrt{n})$ is equivalent to $O(\sqrt{2^k})$.

Since $\sqrt{2^k}=2^{k/2}$, this complexity is obviously exponential in terms of input-length.

$\endgroup$
  • 2
    $\begingroup$ But why is it defined in terms of input length? Every other CS problem I've ever encountered defines time-complexity by the value. It is exponential in terms of input length, but it's sublinear in terms of the value itself, and sublinear in terms of time with respect to $n$ itself $\endgroup$ – Nakano Jan 24 '16 at 14:46
  • 6
    $\begingroup$ @Nakano: The complexity is always calculated by the length of the input. It's just that in most cases, the input is some sort of data structure (for example, an array) of $n$ elements. So the length of that type of input is $n$. $\endgroup$ – barak manos Jan 24 '16 at 15:30
  • $\begingroup$ @Nakano Also, in a lot of cases of computing complexity, regular arithmetic operations are treated as constant time operations. Which, on a physical machine, if you're only ever expecting to deal with numbers that are <32 bits, this is essentially true. However, when talking about the time complexity of factoring numbers, usually the numbers that people are interested in factoring are many hundreds of digits long and so arithmetic operations cannot be done on them in a single "step" on a real processor and so we take the cost into account. $\endgroup$ – Shufflepants Jan 18 at 5:18
3
$\begingroup$

Strictly speaking, it is invalid to ask whether an abstract problem like integer factoring is in P. When deciding whether an algorithm runs in P time, we don't ask about the $n$, the number being factored (or equivalent), we ask about the length of the input. The length of the input depends on exactly how you've chosen to represent it. Instead, we have to ask whether the integer factoring with a particular representation is in P.

Integer factoring with the numbers represented in binary is (as far as we know) not in P. In this case, the length of the input is $\log_2 n$.

Integer factoring with the numbers represented in unary is in P. In this case the number of bits is $n$.

Integer factoring with number represented as a list of numbers from 1 to N is in P. In this case the number of bits is $O(n \log n)$

Why the length of the input? That's just the definition of P.

Typically, we assume when talking about P/NP, that you are using a reasonable representation. What makes a reasonable representation? That's left somewhat underspecified. There is no strict definition for this reasonableness. But representing numbers in unary, or as lists of numbers is clearly not reasonable, as it uses an exponential amount of space compared to using binary.

Ok, what about the maximum of $n$ numbers?

The obvious way to represent this would be using $k$ bits for each number, giving $nk$ bits total. That puts the problem in P. In order for the problem to end up outside of P, the length would have to be something more like $O(\log n)$. But a representation that short couldn't hold the numbers in the list. Whatever problem was being solved there, it would not recognizably be finding the maximum of a list.

To some degree it comes down to: I can represent $n$ in the integer factorization problem with $\log n$ bits without losing information, so we assume that you will. But I can't do the same with the maximum integer problem.

$\endgroup$
1
$\begingroup$

Why do you think the problem is solvable in $n^{1\over 2}$? Keep in mind that you have to find each factor, and testing "Does $x$ divide $y$?" (and computing $y/x$, if so) takes more than one step. (Also, $n$ here is the number of bits of the input, not the input itself. See bof's comment.)


By the way, strictly speaking, we don't know that integer factorization isn't in $P$; we just know that the obvious approaches don't work.

$\endgroup$
  • 1
    $\begingroup$ Why is the definition being changed to the number of bits of $n$ instead of $n$ itself? $\endgroup$ – Nakano Jan 24 '16 at 1:58
  • $\begingroup$ I don't understand why it's not framed as $\sqrt{n}$. You give me $n$ and I will get its prime factorization after having iterated up to $\sqrt{n}$. $\endgroup$ – Nakano Jan 24 '16 at 2:05
  • 1
    $\begingroup$ How do you figure out the primes up to $\sqrt n$ in $O(\sqrt n)$ time? $\endgroup$ – Noble Mushtak Jan 24 '16 at 2:13
  • $\begingroup$ @NobleMushtak en.literateprograms.org/… $\endgroup$ – Nakano Jan 24 '16 at 2:17
  • 1
    $\begingroup$ The $generatePrimeList$ function works in $O(m^2)$ (although that's probably an overestimation). Therefore, The algorithm should run in $O((\sqrt n)^2)$, or $O(n)$. Even then, though, you need to divide each prime out at most $\log n$ times, so it's actually $O(n \log n)$. $\endgroup$ – Noble Mushtak Jan 24 '16 at 2:20

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.