Tag Info

New answers tagged

1

Let's focus on the topic of whether the matrix determinant's $O(n^3)$ floating point complexity of standard approaches (elimination or factorization) can be improved by having "an upper bound". Knowing an upper bound on the determinant of a matrix does not immediately help lower the complexity of its computation. In the case of real (or complex) matrices, ...


2

How about any functions $f$ and $g$ satisfying $f(1) = 1$, $f(2)=0$, $g(1) = 0$, and $g(2)=1$ ?


3

Consider $$ f(n)=\left\{\begin{array}{lll} n & \text{if} & n \,\,\text{odd}, \\ 1 & \text{if} & n \,\,\text{even}, \end{array}\right. $$ and $$ g(n)=\left\{\begin{array}{lll} 1 & \text{if} & n \,\,\text{odd}, \\ n & \text{if} & n \,\,\text{even}. \end{array}\right. $$


1

$$ f(n) = n^2 \sin^2{an}, \qquad g(n) = n^2 \cos^2{an} $$ Then $$ \frac{f(n)}{g(n)} = \tan^2{an}, \qquad \frac{g(n)}{f(n)} = \cot^2{an}. $$ Choose $a = \pi/2$ for the most obvious problems.


4

Just choose $$ f(n)=\frac{1}{|\sin n|}, \quad g(n)=\frac{1}{|\cos n|}.$$ You have that $$ \frac{f(n)}{g(n)}= |\textrm{cotg } n|,\quad \frac{g(n)}{f(n)}=|\tan n|, $$ and none of those are bounded.


0

Using Hadamard's inequality: $$\det(M)\leq\prod_{i=1}^{N} m_{ii}.$$ one can at least state, the the determinants sign is negative if the product sum of the diagonal elements is at most zero. Nevertheless, I'm struggling by myself finding the lower bound. Yours tcsh


1

Is there a way of computing the $n$th number of a Lucas Sequence of the first kind (given parameters $P$ and $Q$) directly, without calculating each prior value in the sequence? Yes (assuming $P^2 \ne 4Q$), but it's unlikely to give any computational advantage: $$U_n(P,Q) = \frac{a^n - b^n}{a - b}$$ where $$a = \frac{P+\sqrt{P^2 - 4Q}}{2}\\ b = ...


2

Hint. One may recall that, by the Euler-Maclaurin formula, as $n \to \infty$, we have $$ \begin{align} \sum_{i=1}^n \frac 1i &=\ln n+\gamma+\mathcal{O}\left( \frac 1n\right)\\ \sum_{i=1}^n \frac {\ln i}i &=\frac 12\ln^2 n+\gamma_1+\mathcal{O}\left( \frac {\ln n}n\right) \end{align} $$ where $\gamma$ is the Euler-Mascheroni constant and $\gamma_1$ is ...


0

Your argument does not work, since context-free languages are not closed under intersection. In fact, the linked article uses $\{a^nb^nc^n: n\in \Bbb N\}$ as a model counterexample, which is somewhat similar to your example. I would recommend a different approach, either trying to directly build a grammar recognizing this language if you think it is ...


0

2SAT is in P, yet whatever you said about 3SAT holds also for 2SAT.


0

Consider sorting. It runs in polynomial time, yet chooses one correct answer from $n!$ possibilities. This is greater than the potentially $2^n$ possibilities for the SAT problem over $n$ variables, for example. So if I understand the outlines of your argument, this would be a counterexample.


1

While the mathematics of this problem are well covered by Mario Carneiro, the reality in the OP is rather distorted. Ignoring the problems with Moore's law as it is. The main issue you will run into very soon is the energy consumed. To further simplify the problem we ignore the fact that energy costs money and just focus on the actual limits of how much ...


1

Let $t_0$ be the current time in years from January 2013, and $n$ be the number of bits in the password. If $y$ is the number of attempts since the NSA started trying to hack your password, then we have the equation $$\frac{dy}{dt}=10^{12}\cdot60\cdot60\cdot24\cdot365\cdot 2^{t/2}=:k\,2^{t/2}.$$ The big number $k$ is for converting the $10^{12}$ ...


1

The volumes of Knuth, "The art of computer programming", are all very interesting. Nevertheless it is also worthy to note E. Dijkstra's book, "A Discipline of Programming", in which he illustrates many important issues and algorithms and methods. It is a beautiful book for a programmer to understand a more disciplined style of programming incorporating ...


-5

My opinion: "A new kind of science" is to science as homeopathy is to medicine.


4

The problem is that asking if something is novel in science is actually very tricky because almost every scientific idea is based on previous work. Therefore, I don't think it is very valuable to question whether something is novel or not because it most certainly is not. However, you can ask if a particular work offers something interesting or particularly ...


8

After reading the reviews that were linked in the comments [1] and @Mark's helpful answer[2][3], I came to a a few conclusions, that answer my questions. First, let's get something out of the way. Stephen Wolfram is definitely a polariser of opinion. Plus his way of presenting himself and his work are not in the canons of the scientific literature and that ...


0

HINT: Suppose that $A$ has $n_A$ states, $B$ has $n_B$ states, and $n=\max\{n_A,n_B\}$. Show that if $A$ and $B$ accept exactly the same words of lengths $\le n$, then $A$ and $B$ accept the same languages. Thinking about the proof of the pumping lemma or the Myhill-Nerode theorem is helpful here.


47

I think the answer to this question is, unfortunately, a little difficult. As many will point out, Wolfram is beyond egotistical and that fact definitely colors the reception of the book. There is a long list of (mostly negative) reviews here. The negativity reaches its apex in the review by Cosma Shalizi. There are some positive reviews as well, though, ...


0

As @SBareS mentioned in the comments the worst case analysis is looking at literally that. For algorithm complexity an algorithm may on average run at a different asymptotic rate compared to artificial input which is designed to require more steps or if randomization is involved a run of the algorithm could randomly choose the worst choice every step which ...


1

Yes. Think about this in terms of evaluating the limit of the exponential over the polynomial. The point of intersection will vary, but the rate of growth of the exponential will always be larger than the polynomial after a certain point. In a more mathematically rigorous sense, think about this as applying L'Hôpital's rule. You will see that the ...


1

Firstly, if your size parameter is $\log_2(n)$--which must be the same for both expressions for consistency--then polynomial complexity would be $$f(n)=\log_2(n)^{0.75}$$ and exponential complexity would be $$g(n)=3^{\log_2(n/2)}=3^{\log_2(n)-1}=O(3^{\log_2(n)})$$ whereby clearly your $g(n)$ grows much faster than your $f(n).$ Taking any constant powers of ...


0

$T(n)2^{-n} = T(n-1)2^{-(n-1)} + c2^{-n}$ and hence $T(n)2^{-n} = T(0)2^{-0} + \sum_{k=1}^n c2^{-k}$.


2

You can solve the recurrence $T(n)=2T(n-1)+c$ directly. The general solution is of the form of the sum of a solution of the homogeneous equation $T(n)=2T(n-1)$ and a particular solution of the full equation. The general solution of the homogeneous equation is: $T(n)=A\times 2^n$. Also as the right hand side has a constant term added to the homogeneous form ...


1

HINT: A word of length $h$ in $A_{n+1}$ is a composition of words of $A_n$, each of which must obviously have length at most $h$. There is a polynomial $P_n$ such that $A_n$ has at most $\sum_{i=0}^nP_n(i)$ words of length at most $h$, so you’re essentially working with an alphabet of size at most $\sum_{i=0}^nP_n(i)$.


1

Big O is up to a constant domination. If $f(x) = x, g(x) = 2x$, then $5*f(x) \geq g(x)$ for large $x$ (in fact, every $x>0$, but this is only an asymptotic statement with big O), for example. So, $g(x) = O(f(x))$. Similarly, $1 * g(x) \geq f(x)$ for large $x$ so we also have $f(x) = O(g(x))$. In this case, we say $f(x) = \Theta(g(x))$.


1

Assuming that the ranking is strict and linear, transmitting it amounts to transmitting a permutation $\sigma$ of $[n]=\{1,2,\ldots,n\}$. For $k,\ell\in[n]$ write $k\prec\ell$ if and only if $k$ precedes $\ell$ in $\sigma$. For each $k\in[n]$ let $$p(k)=|\{\ell\in[n]:\ell<k\text{ and }\ell\prec k\}|\;;$$ $0\le p(k)\le k-1$. The number $p(k)$ specifies ...


0

This is at best a partial answer. For a general finite partially ordered set (i.e. a partial order that is not necessarily a total order), I can think of two things that would reduce the amount of information that would need to be sent. The first is to collapse "similar" elements into a single element. By similar elements, I mean that they are covered by ...


1

There are $\binom{N}{n+1}$ ways to choose the first $n+1$ elements of the list. There are exactly $n$ ways to order these so that the only pair out of order is the last pair: we must pick one of the $n$ elements other than the largest, put it at the end, and precede it by the remaining $n$ elements in increasing (i.e., sorted) order. Finally, there are ...


1

Note that all numbers greater than $N$ are indistinguishable to the program from each other. With no change to running time, we can replace all instructions $X_i = X_i+1$ with $X_i=\min(X_i+1,N+1)$. This way all variables are confined to $\{0,1,2,..,N,N+1\}$. Create a graph of all possible states of an executing program. The vertices are tuples $(X_1, X_2, ...


0

At first substitute $\lg(n)$ by $x$ and show that: $$\lg(x)^k \in o(x^\epsilon)$$ for all $k, \epsilon >0$ when $x \to \infty$. This last inclusion can be proved by the L'Hôpital's rule: $$\lim_{x \to \infty}{\frac{(\lg(x)^k)'}{(x^\epsilon)'}} = \lim_{x \to \infty}{\frac{k \cdot \lg(x)^{k-1} \cdot \frac{1}{x}}{\epsilon \cdot x^{\epsilon -1}}} = ...



Top 50 recent answers are included