# Tag Info

## New answers tagged computational-complexity

1

That you don't create new matrices $D^{(n)}$ but just modify the values in the one matrix. Well, not in one matrix but you have two where one is the previous one ($D^{(n - 1)}$) and the second is the one you compute. When a new $D^{(n)}$ is computed, it becomes $D^{(n - 1)}$ in the next iteration and the previous $D^{(n - 1)}$ (now $D^{(n - 2)}$) becomes a ...

1

We set $h=O(f+g)$. So it suffices to prove that $h=O(\max\{f,g\})$, i.e. that $\exists c>0, n_0 \in \mathbb{N}$ such that $\forall n \geq n_0$: $h \leq c \max\{ f,g \}$ We know that $h=O(f+g)$. By definition that means that $\exists c_1>0, n_1 \in \mathbb{N}$ such that $\forall n \geq n_1:$ $$h \leq c_1(f+g)$$ So, we have $\forall n \geq n_1:$ ...

1

$$h(x)=\mathcal O(f(x)+g(x))\iff \exists \delta>0,\exists C>0:\forall |x|<\delta, \left|h(x)\right|<C|f(x)+g(x)|$$$$<2C\max\{|f(x)|,|g(x)|\}$$ therefore $$h(x)=\mathcal O(\max\{f(x),g(x)\})$$ I let you do the other one, the proof goes in the same way ;-)

1

To show that $O(f+g)\subseteq O(\max(f,g))$, say, let $r$ be an element of $O(f+g)$. Then $r$ is a function of $n$ with the property that there exist positive numbers $C$ and $N$ such that $n \ge N$ implies $|r(n)| \le C(f(n)+g(n))$. Now, note that $$a + b = \min(a,b) + \max(a,b) \le \max(a, b) + \max(a, b) = 2\max(a,b)$$ for any numbers $a$ and $b$. Can you ...

1

IP problems are generally solved by using a relaxation to the (N)LP formulation. Branch and bound algorithms and cutting plane algorithms utilize a relaxation of some sort. Non-Linear Programming is much harder than LP, especially when the feasible region is non-convex, as it can be hard to determine which points are actually optimal. So if you have a ...

2

Quicksort boils down to: Selecting a pivot Separate big list into a "smaller than pivot" list $S_{1}$ and "larger than pivot" list $S_{2}$ Sort $S_{1}$ and $S_{2}$ separately, call result $S_{1}'$ and $S_{2}'$. Combine $S_{1}'$ and $S_{2}'$ and pivot into final, sorted list $S'$. Selecting a pivot randomly is constant time. Hence, it follows that $T(n) ... 0 Note that$f(n) = O(g(n))$iff$f(x) \leq c * g(x)$for some constant$c$and$x \geq x_{0}$. Big-Omega switches the inequality. So if$f(n) = O(g(n))$and$f(n) = \Omega(g(n))$, then we have$f(n) = c * |g(n)|$, which satisfies the definition of$\Theta(n)$. To test this, consider$L = \lim_{n \to \infty} \frac{f(n)}{g(n)}$. If$0 < L < \infty$, ... 2 Run the algorithm repeatedly (and independently) until you don't get '?'. 1 This just adds some information about things you've already mentioned -- I'm quite interested as well in any methods. I note: To the authors’ knowledge, the only known prime generation algorithms for which the statistical distance to the uniform distribution can be bounded are the one proposed by Maurer [19,20] on the one hand, and the trivial ... 0 This looks like the knapsack problem, which is$\operatorname{NP}$-complete. You can easily verify the problems are similar if you consider a related problem where each company offers only one mode of transportation. Then you would have: $$\left[\begin{matrix} C_1\\C_2\\...\\C_i\end{matrix}\right] = \left[\begin{matrix}(s_1, d_1)\\(s_2, d_2)\\...\\(s_i, ... 0 As for asymptotic bounds, note \log n! \in \Theta(n \log n). This is immediate from n^n \geq n! \geq (n/2)^{n/2}. 1 Note that n! = \prod_{i=1}^{n} i \leq \prod_{i=1}^{n} n = n^{n}. So log(n!) \leq log(n^{n}) = n log(n). And so log(n!) = O(n log(n)). 0 Probably you need Stirling's theorem. 0 If G has n vertices, you just want to compare to the path P_{n}. So you reduce HP \leq L, where HP is Hamiltonian Path. So let G be a graph with a Hamiltonian Path. We construct an instance of L with parameters (G, P_{n}). So suppose G has a Hamiltonian Path. As the Hamiltonian path is a path on n vertices, so P_{n} \subset G and L ... 2 A Hamiltonian path is a spanning tree isomorphic to a linear graph. 0 In a certain sense made rigorous elsewhere in a mathematical logic conjecture whose origin I can't remember, every mathematician's proof is expressible in terms of basic semantics that a computer can understand given basic axioms and deduction rules. If you accept that, then no, there is no computer undecidable problem that a mathematician can figure out a ... 0 It is common to find that undecidable problems often have a solution in certain special cases even though there is no general solution. The halting problem is an excellent example; certainly it is possible to prove that (most) programs written by humans intended for a practical purpose do eventually halt. 0 Use the definitions. Say f and g are positive. f is o(g) means: for every constant k>0, for large enough n we have f(n) \le k g(n). f is \omega(g) means: for every constant m>0, for large enough n we have f(n) \ge m g(n). Now try k=1/2, m=2, for example. For large enough n we have$$ 2 g(n) \le f(n) \le (1/2) g(n) $$... 0 No. Little-o and Little-omega are strict inequalities. Big-O and Big-Omega are weak inequalities. So if f(n) \in O(g(n)) and f(n) \in \Omega(g(n)), then f(n) \in \Theta(g(n)). Little-o states that |f(n)| < c * |g(n)| (for some sufficiently large constant c, and all n > n_{0}). Little-omega is comparable, just use a strict greater-than ... 0 Ok, I fear I have now to give it a try. The problem is that solving this requires some understanding of the meaning of the Landau symbols, but I try to make it as elementary as possible avoiding all order manipulation of the terms. First, it does not matter if one uses the \ln or the \log_{10} for asymptotic estimates here, since changing from one to ... 0 In order to prove the asymptotic relationship f \in O(g) you have to choose both constant c and x_0, such that the inequality f(x) \le c \cdot g(x) becomes true for all x > x_0. In your case you can choose c = 8 and x_0 = 4. I'll leave all the rest to you. Just a hint - you can replace x + 2 by 2 \cdot x in this case (for simplicity, ... 0 If you run an elimination tournament among the elements, you can find the largest in n-1 comparisons. The second largest could be any one of the elements that lost to he final winner. How many is that? 1 Since I cannot post a comment I make this into an answer. This answer provides the desired lower bound for finding only the second largest element and provides an algorithm which finds both the largest and the second largest element in desired number of comparisons. So it solves your question. 1 The classes \mathcal{P}, \mathcal{NP} are defined for decision problems. The class \mathcal{NP}-HARD does not contain only decision problems. So \mathcal{NP}-Complete problems are the hardest problems in \mathcal{NP}, but the optimization problems of such \mathcal{NP}-Complete problems are \mathcal{NP}-Hard. Consider for example the ... 0 It's actually co-NP-Complete. Here's the proof. First we have to show that it's in co-NP. This isn't hard, since it's quick to verify a counterexample showing that the two Boolean formulas are not equivalent. Then we have to show a problem known to be co-NP-complete reduces to your problem, which we'll call Boolean Equivalence. We'll reduce the ... 2 No, it is not tractable in the general case. Simply specialize the result to b=0 and A a polytope, and you have maximization of 1-norm in polytope, which is known to be intractable Mangasarian, O., & Shiau, T. H. (1986). A variable-complexity norm maximization problem. SIAM Journal on Algebraic and Discrete Methods, 7(3), 455–461. 0 I don't believe it is. I have a deleted answer sitting here as a scratchpad for me to try some various reformulations to a tractable form, without success. It resembles a saddle-point problem, but the joint convexity of the objective is an obstacle. The inner minimization produces a convex function of a; e.g.,$$\begin{array}{ll} \text{maximize} & ... 1 For each variable y, build two vertices, one for y and one for ~y. Connect both y and ~y to X, the unique global node that is connected in a triangle with T(rue) and F(alse). These connections will ensure that one of {y,~y} gets a color of T and the other gets a color of F. This is what gives you the connection between a coloring and a truth assignment. ... 1 Actually, there is no 3-coloring if the 3 literals are colored as F. This is because the node after the "merge" will be colored as F, while the blank below left of T will be as X. The remaining node (upper left of T) can have no valid color in this case. 3$\let\mr\mathrm \mr{BPP}$is in the second level of polynomial hierarchy by the Gács–Sipser–Lautemann theorem, and it is an easy exercise to show that $$\mr{P^{ZPP}}=\mr{ZPP}\subseteq\mr{P^{RP}}\subseteq\mr{P^{BPP}}=\mr{BPP}.$$ The least trivial of these is the inclusion$\mr{P^{BPP}}\subseteq\mr{BPP}$: let$L_0$be a language decidable by a machine$M_0$... 1 Well you can do this with$2*k$multiplications i.e with$C=2$. The algorithm is outlined below: Initialize$temp = 1$for i=$1$to k do$b_i$= temp temp = temp*$a_i$end temp =$1$for i=k to$1$do$b_i$= temp temp = temp*$a_i$end Example ,$k=4$First Pass$b_1$= 1$b_2$=$a_1$... 0 This is a case of the weapons-target assignment problem: http://en.wikipedia.org/wiki/Weapon_target_assignment_problem 1 Here is a (stronger) result (with an easier proof) which implies yours: Assume that$\liminf |f|\gt0$, then, for every finite$c$,$f+c\in O(f)$. To apply this to your setting, note that the hypothesis that$\lim f=+\infty$implies that$\liminf |f|\gt0$, and that if$f+c\in O(f)$and$f\in O(g)$then$f+c\in O(g)$. Now can you prove the result above? ... 1 First ask "Is 1 occupied?", then, "Is 2 occupied?", "Is 4 occupied?", "Is 8 occupied?", and so on, until you get the answer, "no". This will take$\log_2n$questions (give or take a fraction). You now know$k$such that$n$is between$2^k$and$2^{k+1}$, and binary search inside that interval will get you the answer in another$\log_2n$questions. 1 You're basically looking for a series of questions that resemble a binary search. Binary search runs average O($\log n$) and worst O($\log n$). Questions like, "is position n occupied", should suffice. Make sure each subsequent question tries to cut the problem size in half. Note: Try asking for an extremely large value, if yes, double the value size, if ... 1 Let$A$be$m\times n$and$B$be$n\times p$(assuming both sparse) and let$e_i$be the$i$th column of the identity matrix of an appropriate size. If the matrices are stored by rows, the product$C:=AB$should be computed by rows as well. We have $$\tag{1} e_i^TC=\sum_j\underbrace{(e_i^TAe_j)}_{a_{ij}}e_j^TB$$ so the$i$th row of$C$is given by linear ... 1 The bound$nnz(AB)=nnz(A)nnz(B)$is tight: Take $$A = \pmatrix{1 & 0 & \dots & 0 \\ \vdots & \vdots & & \vdots \\1 & 0 & \dots & 0 }\in \mathbb R^{m_a,n_a}, \quad B = \pmatrix{ 1 & \dots & 1 \\0 & \dots & 0 \\\vdots & &\vdots \\0 & \dots & 0 \\}\in \mathbb R^{m_b,n_b}.$$ Then$AB$is a ... 1 First I imagine that$n$is an integer and that you want to study this problem when$n$goes to$+\infty$. That's probably obvious but better to be sure! Then please write the definition of$2^n = O(3^n)$. That should be something like there exists$C>0$real and$N$integer such that for$n > N$you have$|2^n| \le C|3^n|$. Now what do you think of ... 1 Apply the same techniques I've shown you in your other threads: $$L = \lim_{n \to \infty} \frac{2^{n}}{3^{n}} = \lim_{n \to \infty} (\frac{2}{3})^{n} = 0$$ So$3^{n}$strictly dominates$2^{n}$, and$L = 0$implies your result. Check out this tutorial on complexity for more on the limit test and your calculus techniques: ... 0 To prove$15n^{2} \in \Omega(3 * 2^{n})$, we consider$L = \lim_{n \to \infty} \frac{15n^{2}}{3 * 2^{n}}$. If$L = 0$, then we conclude$15n^{2} \in \omega(3 * 2^{n})$. Little-omega is a strict inequality, and so it implies Big-Omega. Applying L'Hospital's rule, we get: $$L = \lim_{n \to \infty} \frac{30}{3 * (ln(2))^{2} * 2^{n}} = 0$$ I applied ... 2$T(n)=2T(\frac{n}{2} )+nT(n)= 2[2T(\frac{n}{4})+\color{red}{\frac n2}] +n = 4T(\frac{n}{4})+\color{red}2nT(n)=8T(\frac{n}{8})+\color{red}3n...T(n)= 2^kT(\frac{n}{2^k})+\color{red}kn$Finally$\frac{n}{2^k}=1$and$\therefore n=2^k0 According to Maple, \eqalign{m^e &\equiv 14178120117339266261904109624890227407523673482786024455164108238811626728989472\cr &1928886528279400665340976615948053755946789302972467196231829204061441862114262 \cr &11704026304276898946101664519229545142128929712389990917298990673103791915511466 \cr ... 1 An alternative is to use the limit test. Consider f(n) = 8n^{3} + \sqrt{n} and:L = lim_{n \to \infty} \frac{f(n)}{n^{3}}$$Note f(n) \in o(n^{3}) iff L = 0 (and little-o is the strict inequality, which implies Big-O). Similarly, 0 < L < \infty \implies f(n) \in \Theta(n^{3}). And finally, L = \infty \implies f(n) \in \omega(n^{3}) ... 1 Your proof is correct, however all you have to observe is that the degree of the LHS equals the degree of the RHS. :) 2 An example of a correct proof would be:$$\log n!=\sum_{i=1}^n{\log i}\leq \sum_{i=1}^n{\log n}=n\log n$so$\log n!\in O(n\log n)$since$\log n!\leq n\log n$for all$n$. 1 The second algorithm uses less space, but the first does fewer comparisons in general. In both algorithms you compare every node with alphabetically with the target until you find one that’s greater. In the second you also test each of those nodes except the last to see whether it has the desired property; in the first, however, you test only those back to ... 1 The "known" subset-sum problem takes as input a list L of n integers and a target sum A. Partition L into n lists (each containing one of the n integers). Append a zero to each of the n lists. Now, each list contains an integer from L and a$0$. Now, feed the n lists and the target A into an algorithm that solves your problem. If your algorithm solves ... 1 It is just simpler to describe the situation with a single input tape -- in particular, if you want to compare the power or efficiency of machines with differing number of tapes, it is convenient that the format of the inputs to all the machines are the same. But it is not a particularly deep choice -- if you have input on one tape and want it spread across ... 0 Too long for a comment: When multiplying in bases other than$2$you have two different sorts of carries. In base$2$, each individual bit multiplication cannot carry. The only carries you get are when you add the bit multiplications together. In other bases you can get carries in the multiplication step. In base$10$, for example, when multiplying$79 ...

Top 50 recent answers are included