Tag Info

New answers tagged

1

You will get the matrix as follow: First specify the basis on each space, say, the standard one on each: $${\Bbb R}^n={\rm gen}\{e_1,e_2,...,e_n\}$$ and $${\Bbb R}^m={\rm gen}\{e'_1,e'_2,...,e'_m\}$$ Then, map each $e_i$ to get $Te_i$, but since $Te_i$ lives in ${\Bbb R}^m$ hence $$Te_1=a^1{}_1e'_1+a^2{}_1e'_2+\cdots +a^m{}_1e'_m,$$ ...


0

The text is saying that for this algorithnm to work, the coefficients of the objective function must all be positive. It then goes on to state that this is an easy thing to achieve. Let's consider your example: Minimize $Z = -3x_1+5x_2+6x_3-9x_4+10x_5-10x_6$ coefficients: $-3,5,6,-9,10,-10$ Subject to: (1) $–2x_1+ ...


-1

A definition of $RP^{RP}$ is given at Wikipedia. A definition of an oracle is given on the same page here. An oracle $O$ therefore takes an input $I$ and has a list of strings $S$ that produce 'yes' if $I\in S$ and 'no' otherwise. So let $S=\{'no'\}$, and if the output from $RP$ is 'yes', then the output from $O$ is 'no' and vice versa.


1

The number of steps needed to compute $\gcd(m,n)$ is given by the length of the continued fraction of $\frac{m}{n}$, hence the worst case is to compute the $\gcd$ of two consecutive Fibonacci numbers (since $\frac{F_{n+1}}{F_n}=[1;1,\ldots,1]$) and an upper bound for the number of steps involved is: $$ 1+\frac{\log(\max(m,n))}{\log\varphi} $$ where $\varphi$ ...


6

(a) Adding the minimization operator $\mu$ to primitive recursion in effect adds computation with open-ended searches ("do until" loops) to fixed-depth searches ("for" loops). So that's what gives us access to full-power, unrestricted computation. (b) Rosza Péter gives a beautiful example of a function which is computable, takes only the values $0$ and $1$, ...


1

Calculating the primes up to $n$ in $O(n)$ time isn't particularly fast, and nor is it particularly slow. A naive Sieve of Eratosthenes works in time $O(n \log n \log \log n)$ and is very easy to implement. It can be sped up to run faster than $O(n)$ using some wheel techniques. I believe one can reduce the time to $O(n/\log n)$. See Paul Pritchard, A ...


2

Actually, matrix multiplication can be seen as a bilinear map $$K^{n\times k}\times K^{k\times m}\rightarrow K^{n\times m},$$ where $K$ is the ground field. Such a bilinear map can be expressed as a tensor of order 3 of format $(nk)\times (km)\times (nm)$ (any bilinear map $K^{\ell_1}\times K^{\ell_2}\rightarrow K^{\ell_3}$ can be represented by a tensor of ...


1

If you want to learn about algorithms, it is a very good idea to learn programming. It always helped me to understand the algorithms, if I also programmed them. And if you are good with understanding algorithms, programming will not be very hard. As programming languages i recommend python and C/C++


0

This is a partial answer (I don't really know how to answer question 2) Question 1) Yes. Every boolean function can be expressed by a series of gates. Actually even few gates are needed for the completeness. For example the most common restriction is that the pair of gates $not$ and $and$ gives completeness. An other example is that any function can be ...


1

Note that $P$ and $NP$ are defined in terms of Turing Machines. $P$ is the set of languages that can be decided by a deterministic Turing Machine in polynomial time. The class $NP$ is the set of languages where string membership can be verified in polynomial time by a non-deterministic Turing Machine. So it would suffice to show that no deterministic Turing ...


0

I think there are many explanations of what it is, but as far as intuition is concerned I think the following is by far the most satisfying. We see bilinear maps as generalizations of the properties of a product, for instance if $K$ is a field or even a ring then the map $\times: K \times K \to K$ is a bilinear map, and this is the starting point, in a ...


1

In the general case we would recursively divide each $n\times n$ matrix into four $\lceil n/2 \rceil \times \lceil n/2 \rceil$ matrices, adjoining a extra row and column of zeros if $n$ is odd to make the sizes of submatrices whole numbers. The point here is that Strassen's formulas for multiplying a pair of $2\times 2$ matrices does not assume ...


3

This a very good question, and the answer is surprinsingly an open problem in Theoretical Computer Science. In a nutshell: one can do addition in linear time, and the best known upper bound for multiplication is (approximately) $O(n\log n)$. But there is no proof that multiplication cannot be done in linear time. You should look at Is there a proof that ...


0

Essentially, because in order to perform a multiplication, you need many additions: $$ M \times N = \underbrace{M + \ldots + M}_{N \text{ times}} $$ for $M,N$ integers.


1

Page 150 of The Nature of Computation by Moore and Mertens has it; it's a reduction from Subset Sum.


0

In this simple example you are supposed to show that there exist $M \ge 0$ such that $\lim \limits _{n \to \infty} \frac {n^{28}} {2^n} = M$ (in more complicated examples you would have to use $\varlimsup$, but let us not complicate the discussion). Let us show that $M=0$. It is easier and equivalent to compute $\lim \limits _{n \to \infty} \frac n ...


3

Apply l'Hopital's rule 28 times and we have $$\lim_{n\to\infty} \frac{n^{28}}{2^n} = \lim_{n\to\infty} \frac{28!}{(\ln 2)^{28} 2^n} = 0$$ Thus there exists a constant $M$ such that for sufficiently large $n$, we have $$n^{28} \leq M 2^n$$ Choosing $M = 1$ will do. Hence by definition of the big O notation, $n^{28} = O(2^n)$. It is however not true that ...


0

Since $log(n) = o(n)$ as $n \to \infty$, we have $$ \frac{n^{28}}{2^{n}} = \frac{\exp (28 \log n)}{\exp (n \log 2)} \to 0 $$ as $n \to \infty$, i.e. $n^{28} = o(2^{n})$, so $n^{28} = O(2^{n})$.


0

Let's say we have an array of size $2^n$. At each position in the array we store a representation of a subset by: A pointer to some element in the original set. A pointer to a lower index in the array (which is the remaining set) Each index in the array, written in binary, represents the subset in question. Then we can generate all subsets with ...


1

quid succinctly answered this. This graph of log-log size vs. time for some open source implementations shows how trial division (in orange) is exponential time, while AKS (dark green is v6, light green is with additional improvements) gives nice straight lines of slope ~6.4, which fits pretty well with the the expected $O(\log^6 n)$ complexity. The APR-CL ...


2

Polynomial is meant in the input size in bits that is polynomial in $\log n$. The PRIMES is in P gives an $O((\log n)^C)$ algorithm.


2

Let Vertex-Cover = $\{ <G, k> : G$ has a vertex cover of size k$\}$ Given an instance $<G(V, E), k>$ of Vertex-Cover construct an instance $<G'(V', E'), k+2>$ of $K_4$-Cover: 1) Set $V' = V \cup \{x, y\}$. 2) Set $E' = E$ 3) Add the edge (x, y) to E' 4) For each edge $(u, v)$ in E', add the edges $(x, u), (x, v), (y, u), (y, v)$ ...


0

The Monte=Carlo method is actually a FPRAS, at least according to my definition of FPRAS, so that is an example. Barvinok's algorithm is probably too hard to explain without a long answer and some higher level background math, but I do know that Barvinok came up with a (still farily complicated) way to count the number of integer points exactly in a convex ...



Top 50 recent answers are included