Tag Info

New answers tagged

1

There is a combinatorial identity used to count the ways $n$ identical objects can be distributed among $k$ distinct boxes. \begin{equation} \#d = \binom{n+k-1}{k-1} = \binom{n+k-1}{n} \end{equation} To see this, imagine we line up the $n$ items in a long row. Now, we designate each item to a box in the following way: 1) Place $k-1$ dividers between the ...


1

This is a classic counting reasoning, although I'm not sure about how the thesis was done. You want to compute the number of different states of the game. The way I see it: you sum on the total number of armies, because you need to have at least one army on each territory. you cannot have less armies than the number of territories, which is why you start ...


3

The algorithm says to return $d$ if $\lceil q\rceil=q$. In your case, $\lceil q\rceil\ne q$, so we proceed to the "else" part of the statement instead of returning $d$.


0

Your proof is on the right track. These pumping lemma questions end up being proof by contradiction. So, we first must assume something, then contradict it. Here we will assume the $L$ is regular, then get a contradiction. Here is a detailed proof below. The basic idea is we choose a string long enough so that the $y$ in the pumping lemma only had the letter ...


1

The simbology is not so clear to me, but I think that, basically, we have that the conjunct $T_i$ in the $k$-CNF is a disjunction of literals : i.e. boolean vars or negated boolean vars. I assume that the variables $x_j$ are the boolena variables; if so, they occur into $T_i$ as is or negated. We introduce an "auxiliary" function $a_i$ associated to $T_i$ ...


2

Donald Knuth is a mathematician who defined modern computer science. You are looking for his book "The Art of Computer Programming." Be warned though, it is a very challenging book to read. Another book that covers combinatorics and has a chapter on algorithms and algorithmic complexity would be Miclos Bona's "A Walk through Combinatorics," if you want ...


2

Two standard books are Introduction to the Theory of Computation by Michael Sipser and Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft et al. Both follow the standard format of definition, theorem and example. You can't go wrong with either of them.


1

If you can do this in time $O(f(n))$, then you can factor semiprimes (i.e., $n$ of the form $pq$, where $p$ and $q$ are both primes) in time $O(f(n)\log n)$. To see this, note that if $n=pq$ (with $p<q$), then for all $b<p$, the number of divisors of $n$ less than or equal to $b$ is odd (just $1$), whereas if $p\leq b < \sqrt{n}$, then the number of ...


0

Not an answer, but it must be formatted in a way that a comment cannot hold. If you continue reading, the author defines this notation: Here, $\langle \cdot \rangle_q$ means the expectation or mean under the density $q$ and $D(\cdot\ ||\ \cdot)$ is the cross-entropy or Kullback-Leibler divergence between the two densities. I have taken ...


0

In addition to martini's answer, it's also useful to write that $n = e^{\log n} = o(\log n ^{\log n})$ because essentially as $n \to \infty \ \frac{f_1(n)}{f_2(n)}$ converges to $0$, so $f_1(n)$ is of a lesser order than $f_2(n)$.


0

The question is, wheter $n$ can be written as $n = f(n)^{\log n}$ where $f$ is a function such that $f\in O(\log)$. This is true, as $$ n = 2^{\log n}$$ an the constant function $f(n) := 2$ has $f \in O(\log)$ as $\log$ is unbounded.


2

Assuming $k,n \in \mathbb{Z}_{>0}$ throughout. X(n) $$\ln n = \int_{1}^n \frac{\mathrm{d}x}{x} \leq \sum_{k=1}^n \frac{1}{k} \leq 1+\int_{1}^{n-1}\frac{\mathrm{d}x}{x} = 1+ \ln (n-1) < 1+\ln(n)$$ Therefore $X(n) \in O(\log n)$. Y(n) We find the largest possible value of the summand by finding the largest possible value of the expression as if the ...


0

I don't know how to use the integral test. As suggested by @Eric and others, I am trying to answer my question. $$\begin{equation}\begin{split}1\leqslant k\leqslant n&\Leftrightarrow\dfrac{1}{n}\leqslant \dfrac{1}{k}\leqslant 1\\&\Leftrightarrow1\leqslant X(n)\leqslant n\\&\Rightarrow X(n)\in\cal{O}(n).\end{split}\end{equation}$$ which is ...


1

The halting set $K = \{e \mid \varphi_{e}(e) \downarrow\} \subset \mathbb{N}$ is not many-one reducible to its complement. For if it were, that is if there were a total computable $f\colon \mathbb{N} \to \mathbb{N}$ such that $x \in K \Leftrightarrow f(x) \notin K$, then we could decide if $e \in K$ by simultaneously watching $\varphi_{e}(e)$ and ...


0

I am guessing at the interpretation to this question. if predicate H(x) become false when a program with code r(x) halt on input l(x), then H be a computable predicate Suppose the range of $l(x)$ is all programs. Suppose $r(x)$ is a simulator. Suppose $H(x)$ is the predicate "$l(x)$ runs forever without stopping." When $r$ stops the simulation of ...


3

Let us consider the more general case of the equation $$x \log(x)=n$$ As mentioned by user1337, almost from definition, the solution is given by Lambert function $$x=\frac{n}{W(n)}$$ Now, let us consider the case where $n$ is just huge as in your case. There are quite good approximations of Lambert function for such a case. For example, $$W(n) \simeq ...


1

The solution can be expressed in terms of the Lambert W function as: $$n=\frac{1000000000 \log (2)}{W(1000000000 \log (2))} \approx 3.96201\times 10^7.$$


-1

There are $64^3 = 262144$ bits, so that there are only $2^{262144}$ possible cubes, which is around $10^{79000}$. Thus, it's not very feasible to do any sort of computation involving looping over all possible cubes.



Top 50 recent answers are included