# Tag Info

## New answers tagged computational-complexity

0

Division requires 2 numbers. Therefore when we do that operation over and over again we obtain a square table. The area of that square is the cost of operation, I believe.

0

We have \begin{align} \Omega = \Sigma_AV_AU_B\Sigma_B &&AB = U_A\Omega V_B \end{align} Only submatrix $\bar{\Omega}$ formed by first $k$ rows and first $l$ columns of $\Omega$ will contain nonzero elements, where $k$ is the rank of $\Sigma_A$ and $l$ is the rank of $\Sigma_B$. If $\bar{\Omega}$ is smaller matrix than $AB$, then one can compute SVD ...

0

The first step is to make sure you understand the meanings of $$f(n) = O(g(n) \mbox{ as } n\to\infty$$ and $$f(n) = \Theta(g(n) \mbox{ as } n\to\infty$$ The former means that there is some constant $C > 0$ and some number $n_0$ such that whenever $n > n_0$, $$|f(n)| leq |C g(n)|$$ the big theta notation means that $$f(n) = \Theta(g(n)) \mbox{ ... 1 Think of it this way: In the most inner loop, the loop goes from k=1 to j with one operation for each value of k, which is j operations. In the inner loop, the loop from j=1 to i with j operations for each value of j, which is:$$\sum_{j=1}^i j=\frac{i(i+1)}{2}$$In the outer loop, the loop from i=1 to n with \frac{i(i+1)}{2} ... 3 Their "polynomially reduces" means polynomially Turing-reduces, and their "polynomially transforms" ​ means polynomially many-one reduces. In standard terminology, which I'll use for this answer, reduce/reduces/reduction/reductions by default refer to many-one. "using g" ​ / ​ "Turing reduction" ​ ​ ​ mean the same thing, and are defined via oracle ... 1 One could enumerate all the algorithms (the set they form is countable) in a given language in some order of increasing length, and the strings that are outputted by these algorithms then have known Kolmogorov complexity. In general, there is no way to compute the Kolmogorov complexity of a given string. Of course, one runs into the problem of non-... 1 OK, so this a brave attempt at answering my own question: Upon a graph G (an input for Hamiltonian circuit), the reduction will check if G has more than one connected components, and if so, will output a graph with only two vertices and one edge, i.e. with no Hamiltonian circuits anywhere. If G has only one connected component, the reduction will ... 1 Conversion between different bases turns out to be a useful way to talk about various pathological functions in analysis. Some examples of this: The Cantor function c: the base-2 expansion of c(x) is closely related to the base-3 expansion of x. The Conway base-13 function f: the base-10 expansion of f(x) is closely related to the base-13 ... 0 Their use is precisely the use you have for base 10: they provide a means of representing numbers concretely. The only difference between 17_{10} and 10_{17} is that you are accustomed to the former representation rather than the latter to represent the number of periods in the quoted symbol ".................". 1 We use base 60 for time and for degrees. I don't know any practical use of base 12, but it would certainly be nicer than base 10. For instance, in base 12 the number 1/3 is not periodic: you have$$1/3=4/12=4\times 12^{-1}=0.4_{12}.$$0 The theory for developing and computing the binary or hexadecimal representation of a number applies equally well to other bases. They may or may not be useful. If some species of alients have 12 fingers they may find base 12 useful. Having too large base has one practical difficulty: finding names for the numbers and remembering them. Too small a base ... 6 Nilpotent matrices For example, if A \neq O_n and A^2 = O_n, then A^k = O_n for all k \geq 2 and$$\exp(A) = I_n + A + \dfrac{1}{2!} A^2 + \dfrac{1}{3!} A^3 + \dfrac{1}{4!} A^4 + \cdots = I_n + A$$Idempotent matrices For example, if A^2 = A, then A^k = A for all k \geq 1 and$$\begin{array}{rl} \exp(A) &= I_n + A + \dfrac{1}{2!} A^2 ...

3

Circulant matrices should be able to be exponentiated in less than $n^2$ time. You can diagonalize them via the FFT and then exponentiate the diagonal matrix. EDIT: I believe strongly non-singular Toeplitz matrices can have their exponentiation well approximated quickly enough by combining the results of http://www.sciencedirect.com/science/article/pii/...

1

Given a word $u=u_0\dotsm u_{n-1}$, it has $O(n^2)$ factors. Determining which ones belong to $L$ is therefore poly-time. From these you construct an oriented graph with the occurences of the factors in $L$ as vertices and with edges $u_k\dotsm u_{\ell-1} \longrightarrow u_\ell\dotsm u_{m-1}$. Then $u\in L^*$ if a suffix of $u$ is reachable from its prefix. ...

1

Is it meaningful to look for "elegant" representation of mathematical objects? OMG, yes. I would replace "meaningful" with "useful" though Is it possible to measure elegance quantitively? I.e., can we formalize such search? Is Kolmogorov Complexity related? Low K(x) is useful, but the lowest K(x) is random, and that's not useful or ...

3

tl;dr: the keyword is enumeration. That is, you know that for any $x$, if there is a witness $y$ proving $x\in {\sf R}$ then it is small, so you can afford to try out all possible witnesses. Stop reading here is you only wanted a clue. Outline: What it means is that the problem $R\in\sf NP$ satisfies the following. There exists an algorithm $M$ such that ...

2

It's not just sloppy, but downright false. Please tell your professor that he/she is wrong. Counter-example: Let $f(n) = \frac12 \log_2(n)$. As $n \to \infty$, clearly $f(n) \in Ω(\log_2(n))$ but $2^{f(n)} \in o(n)$.

Top 50 recent answers are included