# Tag Info

0

I have implemented a solution in javascript if anybody is interested: function findOptimalDistribution(Z, z) { // Make a working copy var Y = Z.slice(0); // Add dummy element so the 'lowest' value is 1, increment z accordingly Y.unshift(1); z++; // calculate sum of Y var R = 0; for(var i = 0; i < Y.length; i++) { ...

-1

It's easy to calculate the value of a CNF logic formula given the valuation (this is in PTIME). We don't know if it is hard to check the satisfiability of CNF logic formula (i.e. whether there exists a valuation that makes the formula true). It is equivalent to the famous $P = NP$ problem. The best algorithm we know for checking 3-SAT is not polynomial, ...

0

Neither $O(), \Omega()$ nor $\Theta()$ holds. Clue for proof: for $n=4k+1,\space sin(\frac{n\pi}{2})=1$ and then $f(n) = n$. That last argument is sufficient to show that $f(n)\neq O(g(n))$. A similiar argument($n=4k+3$) will yield $f(n)\neq \Omega(g(n))$ which will evidently lead also to $f(n)\neq \Theta(g(n))$.

0

You have: $\sum\limits_{i=1}^{n}x_i-z=\sum\limits_{i=1}^{n}y_i$. Hence, you are looking for a vector $y$ in $\mathbb{N}^{n}$ sorted in the ascending order such that $\sum\limits_{i=1}^{n}y_i=z^{\prime}$, where $z^{\prime}=\sum\limits_{i=1}^{n}x_i-z$=constant. Therefore there exist many $y$. You can choose the elements of $y$ arbitrarily as you want such ...

0

There are more solutions. Do you insist that the $x_i-y_i$ be monotonic as well? It appears you accept $0 \in \Bbb N$, so $Y$ could be $\{0,0,48\}, \{0,3,45\},\{1,1,46\}$ or many others.

0

Here's a link to a thorough and authoritative source: http://www.cs.utexas.edu/users/inderjit/public_papers/HLA_SVD.pdf Inderjit Dhillon is a leading expert on eigenvalues.

0

Let $T(N,C)$ be the time it takes the algorithm to run. Your first specification says that $T(2N, C)$ = $3T(N,C)$. Your second specification says that $T(N, C+1) = 2T(N,C)$. This means that $$T(N,C) = 2^{C-1} T(N,1) \approx 2^{C-1} 3^{\log_2(N)} T(1,1)$$ So the time complexity is $$O\left(2^C 3^{\log_2 N}\right) = O\left(2^C N^{\log_2 3} \right) = ... 0 You should exclude the trivial case of p being a constant function. The precise statement is: For every negligible function \mu and for every nonconstant polynomial p with positive leading coefficient, the composition f = \mu\circ p is negligible. Indeed, for every c>0 we have$$|\mu(p(x))| < \frac{1}{p(x)^c} \tag{1}$$whenever p(x) ... 0 I think it is extensively studied under oracle turing machines. Here is an example from this book. Let EXPCOM = \{<M,x,1^n>: M outpits 1 in 2^n steps.\} Now consider P^{EXPCOM}/EXP along with your definition. Clearly EXP\subseteq P^{EXPCOM}. Now for two problem (b,b') which is in P^{EXPCOM} and if there is a polynomial time ... 1 On the the wikipedia article for invertible matrices they show how you can design matrix inversion by blocks, which obtains the same complexity as multiplication. Pretty neat. 0 Given \lambda and r, consider all possible combinations of r integers that have a sum that does not exceed \lambda. What is the maximum possible product? This maximum is attained when the sum is equal to \lambda: suppose otherwise, that \sum_i u_i < \lambda, where \prod_i u_i is a maximum. Then just replace u_1 with u_1+1. This gives a ... 1 The product \prod_{i=1}^r u_i is at a maximum when the v_i's are as far apart as possible. (If the v_i's are close together, then their gaps u_i would be smaller.) The only way for the v_i's to be as far apart as possible is if they are spaced \frac{\lambda}{r} apart. Thus, \prod_{i=1}^r u_i is at most ... 0 I'm using the naive way, and I found that the loss of precision is significant for small distances (like between points (1,8) and (16,3)) for instance. The error is very significant, try for yourself. 2 You have to estimate the general term, throwing away some terms that are negligible and multiplicative constants. In your example, you want to estimate \sum_{i=1}^n (4i-2). This is equal to 4(\sum_{i=1}^n i)-2n=4\frac{n(n+1)}2-2n=2n^2=O(n^2) (it is even \Theta(n^2)) 0 Actually, we do have n^4\in\Omega(n^3). That is,$$ \exists k>0\exists n_0\forall n>n_0\colon kn^3\le n^4.$$In fact you can pick k=1 and n_0=1. On the other hand assum n^2\in\Omega(n^3). That is,$$ \exists k>0\exists n_0\forall n>n_0\colon kn^3\le n^2.$$But since k>0 we can find n with n>\frac 1k (and at the same time ... 1 No the proof is not correct. The function witnessing A\leq B and the one witnessing B\in RE have no reason to be the same. Also none of these two functions have any reason to be inversible (so your f^{-1} does not exist). Here is a proof: Assume A\leq B, witnessed by a computable function f:\Sigma_A^*\to\Sigma_B^* with x\in A\Leftrightarrow ... 1 Your problem as stated here is non-convex and there is no polynomial time solution for it, unless P=NP (to the best of my knowledge about this problem), but you can approximated it with a convex optimization program as I explain in the following: Your non-convex program can be formulated in the following form: Let v\in R^n and let e_i be the ith ... 0 Did you understand the meaning of the big-O-notation? In computational complexity, we want to compare functions as n \to \infty, and see which one wins for large enough n. In all types of winning the winner must not lose from a certain size of n onwards. f \in O(g) means that f wins g for all large enough n if f has a fast enough CPU. f \in ... 1 I begin with the answers and then justify them: 1) F T F F 2) T T T T 3) T F F T 4) T F F T 5) F T F F Given 2 real-valued functions f and g, we say f(n)=O(g(n)) if there exist constants k>0 and n_0>0 such that 0\le f(n)\le k\cdot g(n) for all n \ge n_0. Given 2 real-valued functions f and g, we say f(n)=\Omega (g(n)) if ... 0 f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x_0 such that for all x>x_0 we have |f(x)|<=M|g(x)|. 0 In computational complexity theory you usually talk about the decision versions of problems (see for example the Wikipedia article on NP). The decision version of the travelling salesman problem is: Is there a travelling salesman tour of length at most L. A solution to this decision problem can be easily checked by summing the costs of all used edges and ... 0 Typically in math, O(f(n)) is taken to be a set of functions. In this context, O(f(n))-O(f(n)) would be set-difference, which would obviously be \emptyset. I feel like what you really meant to ask was, "If f,g \in O(h), is f-g \in O(h)?" The answer is yes, which is simple to show:$$f \le M*h \;\text{and}\; g \le N*hf-g \le (M-N)*h ...

0

The big-O classes are closed under addition/subtraction of functions, which is what I assume you mean (i.e. if two functions $g$ and $h$ are both $O(n^2)$ say, then so is $g+h$ and $g-h$ in general).

2

Indeed we could resolve the $k$-clique problem for fixed $k$ by inspecting $\binom{n}{k}$ subgraphs. However, the number $k$ is considered an input to the problem too. In the $k$-clique problem, the input is an undirected graph and a number $k$, and the output is a clique of size $k$ if one exists (or, sometimes, all cliques of size $k$). -- Wikipedia ...

Top 50 recent answers are included