New answers tagged

1

This is studied in the theory of computability, especially in computable analysis, because the choice of the representation of real numbers determines which functions on real numbers are computable. What follows is based on Computable analysis: An introduction by Klaus Weihrauch. See also The Representational Foundations of Computation (draft) by Michael ...


0

Yes. There's nothing preventing functions being in all three at the same time, and it's really easy to verify that your function indeed is.


0

There are 3 cases to the Master theorem for solving the recurrence $T(n)=aT(n/b)+f(n)=3T(n/2)+n^2 / (\log n)$. If you draw out the recursion tree, the cost of the root is $f(n)$ and the cost of all the leaves is $n^{\log_b a}$. We compare these two costs and we get the three different cases for the Master theorem. Since the cost of the root $f(n) = n^2 / ...


0

This seems to be true for non-negative functions, and generally pretty false. Suppose for all $n\geq N$, we have a constant $c>0$ such that $c\log n \leq |f(n)|$. Since $2^x$ is an increasing function we can apply it across the inequality and preserve the validity of the statement: \begin{align*} 2^{c\log n} &\leq 2^{|f(n)|} \\ 2^cn &\leq ...


1

No, there is no connection of the kind you seem to be imagining. 2-SAT and 3-SAT are both about satisfiability in ordinary two-valued logic. They differ in which shapes of formulas you can ask to have satisfied, but satisfying that formula is a matter of ordinary true/false logic in both cases. The "canonical" satisfiability problem in computational ...


1

This relation can not be used with the Master Theorem because $f(n)=n\log \log n$ does not meet any of the cases. Is $f(n)=O(n^{1-\epsilon})$? No, because $n\log \log n$ grows faster than $n$. Is $f(n)=\Theta(n\cdot\log^k n)$? No, because $n\cdot\log\log n$ grows slower than $n\log n$. Is $f(n)=\Omega(n\cdot\log^k n)$? No, because $f(n)=o(n\log n)$ and ...


2

For intuition: the $n$th Busy Beaver number is basically a bound on the time a sufficiently small halting machine can take. In order to verify the $n$th Busy Beaver number, we must execute some algorithm to check it. Our algorithm can be executed by some halting machine (indeed, if it doesn't halt, then it's not fit for purpose because it doesn't answer ...


2

Usually, the definition is $\lambda (n)=(-1)^{\Omega(n)} $ where $\Omega(n)$ is the number of prime factors of $n$ counted with multiplicity. If $n =\prod p_n^{k_i} $ then $\Omega(n) =\sum k_i $. Therefore the time to compute $\Omega(n)$ is at most the time needed to factor $n$, so you can look at articles like this to get an idea of what is currently ...


1

There is a simple linear time algorithm to do this, provided you already have the assignment. First let's assume you have just a single clause, say $(x_1 \lor \overline{x_2} \lor x_3)$. Starting at the left, first substitute $t_1$ from the assignment for $x_1$, giving $(t_1 \lor \overline{x_2} \lor x_3)$. Now, substitute the next literal, giving $(t_1 \lor ...


0

I know this question was posed 5 months ago but I thought I would add something. Not sure if this will increase computing time but, $\lambda(n)=i^{\tau(n^{2})-1}$, where $\tau(n)$ is the divisor function and $i$ is the imaginary unit. From this of course the summatory Liouville function is $L(n)=\sum_{j=1}^{n}i^{\tau(j^{2})-1}$. Perhaps the divisor function ...


2

NP Complete need not mean safer, since you want strength not only in the worst case (for the attacker) but in all cases. Some cryptosystems based on NP complete problems (most notoriously based on the knapsack problem) have been broken. Having said that, cryposystems based on the Discrete Logarithm problem in prime order groups, as well as those based on ...


4

That is a simple greedy algorithm. It will always create a solution, and likely creates reasonable solutions. But it won't always find the best solution. And indeed it wouldn't take much work to create a solution where it will be forced to find the wrong path. (Basically you'd use the edges that are not part of either the best or the wrong paths to force ...


0

Despite the caveats you have gotten, the intended answer goes something like this. For the second part, if you can do $n=100$ of an $n^2$ algorithm on the old machine, you can do something like $100^2=10000$ operations in a minute. The new machine will do $100$ times this, which is $1,000,000$. We now need to find the $m$ such that $m^2=1,000,000$ and we ...


1

One must make several assumptions to answer your question precisely. But making all the simplest assumptions, one has: $k\ n \log{n} = 23$ and hence $k \approx 3.3\ 10^{-3}$. Then $k 10000 \log{10000} = 307$ second. As for assumptions... note that a function that is in the class ${\cal O}(n^2)$ is also in ${\cal O}(n^3)$; conversely, some functions in ...


1

You cannot know the exact time of a given order, but let me reformulate your question to be, what is the upper bound a given order for a given value of $N$. For example, If $N = 100$, what is the Upper bound time of $O(N^2)$? We know that $O(N^2) < O(N Log(N))$ Then an upper bound of $O(N^2)$ with $N = 100$ is $100 \log(100) = 100\cdot ...


-1

It is $O(x^k)$ because it is $o(x^k)$ for any $k>0$. This results from the basic high school limit $$\lim_{x\to\infty}\frac{\log x}{x}=0$$ and the functional properties of the logarithm.


0

I think the trick is that the inner cycle (k) executes k * n^(1/3) * log (n) = n until the cycle breaks. So K = n^(2/3)/log(n) and because the outer cycle executes O(log n) then we can say that the overall time complexity is O(n^(2/3)).


1

You could say $\lim_{x\to\infty}a^{1/x}=1$, but has been already noted there is no specific value for $x$ that results in $a^{1/x}$ equaling $1$.


1

If $a =1$, any $x\neq 0$ will do. Otherwise, you would need $1/x=0$ which of course never happens (in the usual $\Bbb{R}$)


5

Well, since $\frac 1x \log a = 0$, $a$ must be equal to $1$ and $x$ can be absolutely any real number whatsoever!


2

The time complexity of the innermost loop is proportional to $n-j+1$. Then, assuming that the assignment $j:=i$ indeed causes a loop exit, the intermediate loop executes at most twice every time it is entered, for $j = i$, and possibly $j=i+1$. So the total cost is proportional to $(n+n-1)+(n-1+n-2)+\cdots (2+1)+1=n^2$.


12

In fact, $\mathbf{P}=\mathbf{NP}$ is an arithmetical statement. What logicians mean by that is that it can be expressed (or, more precisely, a statement "fairly trivially" equivalent to it can be expressed) using only the language of first-order arithmetic, that is, as a formal statement built from {atoms of the form $s=t$ where $s$ and $t$ are expressions ...


2

In general, if I can enumerate a list of computable functions I know to be total, then I can enumerate that same list without repetition. Here's how to do this. Suppose I have an enumeration $\{f_n: n\in\mathbb{N}\}$ of some total computable functions. Say $f_n$ looks new at stage $s$ if for every $m<n$, there is a $k<s$ such that ...


2

You are correct. There might be an $NP$-complete problem that can only be translated into Hamiltonian path problem in $\Omega(n^{10})$ time, for instance. In which case an $\Omega(n^{10})$ translation and an $O(n^4)$ solution gives a total time of $\Omega(n^{10})$. The only thing you can be certain of is that the final time is bounded by a polynomial.


1

If you write your algorithm out in English, it is something like the following: while the number is not 1, try dividing it by every number in order, beginning with 1. Every time we find a factor, divide the original number by the factor, then continue on. To take 187 as an example, you first try all divisors less than 11 unsuccessfully, then find that 11 is ...


1

I would leave a comment but don't have the reputation: check out http://www.math.udel.edu/~lazebnik/papers/dioph2.pdf, which also looks to have several useful references (in particular http://www.math.tamu.edu/~rojas/kannanbachemhermitesmith79.pdf for algorithms to compute Smith normal form).


1

Here's a start on improving the $81^{16}$ upper bound. The total number of ways that gobblets can be placed on the board is no more than $$\left({16\choose0}+2{16\choose1}+4{16\choose2}+8{16\choose3}+14{16\choose4}+20{16\choose5}+20{16\choose6}\right)^4\\=277{,}993^4\approx5.97\times10^{21}$$ That is, a state of the board is determined by specifying, for ...



Top 50 recent answers are included