1
$\begingroup$

I'm currently dealing with complexity estimates of various algorithms and the connected mathematical problems. Up until now, I had in mind that problems such as integer factorization and the discrete logarithm problem are among the hardest problems we know about. However, I've done some concrete examples which to me indicate that even something as mundane as matrix multiplication can be more difficult than these particular problems. Here are my observations:

Compare the brute force factorization of a semiprime $n=p \cdot q$ to the 'schoolbook' matrix multiplication algorithm. We can multiply all numbers below $\lfloor \sqrt{n} \rfloor$ with each other and we're guaranteed to find $n$ among the results; so this has $O(n)$ as a worst case complexity. Naive matrix multiplication, however, has $O(n^3)$ as a worst case complexity. So is naive matrix multiplication really harder than factoring semiprimes?

I had in mind that matrix multiplication can be done with polynomial-time algorithms whereas integer factorization has subexponential algorithms at best. If we view the complexity of the above factoring algorithm relative to the input-size in bits, we arrive at $O(2^b)$ where $b$ is the bitsize of $n$, so there is an argument for 'exponentiality'. But then the same argument can be made for the naive matrix multiplication, so it can viewed as an exponential-time algorithm as well.

Are these observations correct, or am I confusing something? As it stands, my traditional view has been turned on its head, but I don't wholly trust these arguments yet...

Thanks for any help!

$\endgroup$
0
$\begingroup$

Your intuition to examine the complexity in terms of the input size is correct. In this sense, your factoring algorithm is $\Omega(2^b \, M(b))$, where $M(b)$ is the time it takes to multiply two $b$-bit integers.

But an $n \times n$ matrix of $n$-bit integers has size $b = n^3$, so matrix multiplication takes only $O(b\,M(\sqrt[3]{b}))$ time.

In essence, your confusion is caused by $n$ meaning different things for the two problems. $O(n)$ and $O(n^3)$ aren't comparable when the $n$s are measuring different things. Any algorithm that takes time proportional to the numerical value of the input is already exponential in the length of the input.

$\endgroup$
  • $\begingroup$ thanks, that makes sense! But in this case, the O-notation can be a bit confusing, since it is sometimes just used to count the number of operations while ignoring the input size. $\endgroup$ – polarbear Aug 18 '14 at 12:34
  • $\begingroup$ @polarbear Always try to be aware of what the notation is measuring and what the parameters are. O notation on its own is ambiguous, but good authors will say things like "sorting takes $\Omega(n\,\lg n)$ comparisons for a list of $n$ elements". Saying "sorting is $\Omega(n\,\lg n)$" is underspecified. $\endgroup$ – Tavian Barnes Aug 18 '14 at 15:06
0
$\begingroup$

Number of entries in a matrix or other complex object is more like number of digits than it is like number: a 100x100 matrix with 32-bit entries is 320,000 bits, not 50 bits (as "a 32 bit number times ten thousand" would fit in). So the argument that your number -> number of bits transformation makes it harder doesn't hold water: the size of the matrix is already directly associated with the number of bits.

$\endgroup$
  • $\begingroup$ ah, I see; so the thing is that in this calculation, $n$ just stands for the number of rows/columns but is itself not used directly in the algorithm (whereas the entries of the matrix are); that's why the transformation to number of bits doesn't work; or that's how I understood your answer. $\endgroup$ – polarbear Aug 18 '14 at 12:38

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.