Tag Info

New answers tagged

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

First note that recognizing the form for the worst case (equality) here as $$ T(n)=a T(\tfrac n b)+f(n) $$ we have $a=34,b=17$ and $f(n)=17n=O(n^1)$ and $$ 1<\log_{17}{34}\approx 1.24465 $$ Thus by the Master Theorem we are in case 1 and have $$ T(n)=\Theta(n^{\log_{17}(34)}) $$ for the case of equality. If we were to arrive at this conclusion by ...


0

Assume we have $T(x)\le cx^{\alpha}+\beta x$ for $x<n$ (with $c\ge0$). Then the recursion shows us $$ T(n)\le 34 c(n/17)^\alpha+\beta\frac n{17}+17n=\frac{34}{17^\alpha}cn^\alpha+(\frac\beta{17}+17)\cdot n$$ so that the desired induction steps works provided we have $\frac{34}{17^\alpha}\le 1$ and $\beta\ge \frac{289}{16}$. Use this to determine suitable ...


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}$ ...


0

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 ...


7

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.


46

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}}} = ...


1

That sounds like a simple adder with carry. If $x = (x_{N-1} \cdots x_0)_2$, $y = (y_{N-1} \cdots y_0)_2$ then $z = x + y = (z_p \cdots z_0)$ via \begin{align} z_0 &= (x_0 + y_0) \bmod 2 \\ &= X_0 \dot{\vee} Y_0 = (X_0 \wedge \neg Y_0) \vee (\neg X_0 \wedge Y_0) \\ c_0 &= X_0 \wedge Y_0 \\ z_{k+1} &= (x_k + y_k + c_k) \bmod 2 \\ ...


0

Your objective, clarified through reasonable assumptions, is not possible. Any algorithm that uses only bitwise operations (I am assuming negation is meant to be bitwise negation), will act the same on corresponding bits regardless of their values. So, if both leading bits are zero and need to end up being one, while both lowest bits are zero, the algorithm ...


1

I will assume that by "affectations" you are referring to instructions, I am not familiar with the use of that word in complexity theory. Also, note that $N$ is your input for this question to make sense, and so it is slightly confusing to describe it as a global constant, even though the program treats it that way. Proceed inductively on the maximum loop ...


2

The answer lies in Shannon entropy and Huffman encoding. First let's discuss Shannon entropy. The Shannon entropy (in bits) of a random variable $X$ with possible values $\lbrace x_1, \ldots, x_n\rbrace$ is $$ H(X) = E(-\log_2(P(X)) = - \sum_{i=1}^n P(x_i)\log_2(P(x_i)) $$ Intuitively, the Shannon entropy represents the average amount of information ...


0

This is, unfortunately, an NP-hard problem. It is a special case of the general quadratic maximization problem \begin{array}{ll} \text{minimize} & v^T Q v \\ \text{subject to} & v_i^2 = 1, ~i=1,2,\dots, n \end{array} where, in this case, $Q=uu^T$. The class of problems for general $Q$ is of considerable academic and practical interest. I found these ...


0

If you have an explicit expression for the number of operations, the computational complexity (in the usual big O notation), is the term that eventually dominates the others. If there are multiple positive maximal terms that do not diminish with respect to each other, choose any of them. So your expression suggests a computational complexity of O(N) (drop ...


2

Assuming the definition is really $$ \Xi_A = \{ n \in N \mid \exists k \in A: k^2 \leq n \} $$ (because $\exists k^2\in A$ is not syntactically well-formed), then the answer is (I): $\Xi_A$ is decidable no matter what $A$ is. This is a well-known family of "trick questions", where the underlying point is that whether a set is decidable (or not) or r.e. (or ...


0

In this video you can find the answer to your question. https://www.youtube.com/watch?v=zO0TbgO6QUg Many Solutions for http://www.cs.utsa.edu/~wagner/CS3343/ss/ss.html https://gist.github.com/maxtuno/7dc9c76af54934f61558 An execution with time Problem: 2618000 [10207, 11296, 11587, 12426, 12823, 13174, 15859, 15899, 16006, 16489, 16493, 17285, 18091, ...



Top 50 recent answers are included