# Tag Info

## New answers tagged computational-complexity

2

According to Maple, there are a number of values of $n < 50000$ for which $N(n) = 22$: > with( GroupTheory ): > select( n -> NumGroups( n ) = 22, [seq]( 1 .. 50000 ) ); [6321, 9075, 9765, 18135, 18669, 19215, 27075, 31017, 31605, 35685, 40053, 45045, 46431, 47565, 49539] There is a conjecture that $N$ is surjective, but to my ...

1

In this book, it proved there exists a Elementary function $C(a,b,c,d)$ such that for every $n$ and $k$: $$\phi_n^k(a_1,...,a_k)=r\Leftrightarrow\exists q\:C(n,<a_1,...,a_k>,r,q)=1$$ and $<a_1,...,a_k>=\prod_{i=0}^{k}P_i^{a_i+1}$ So we can define $U(n)=\pi_1(n)$, and $$T(n,x,y)\simeq C(n,x,\pi_1(y),y)$$ $<n,m>$, $\pi_1(n)$ and $\pi_2(n)$ ...

0

It is O(n^2) because in any graph representations like adjacency matrix or adjacency list you will take O(n^2) time to check everything.

0

The time complexity of the third loop can be bounded more tight. You already observed that the outer loop is executed exactly $m$ times. For each $j$ the inner loop is executed $b[j]$ times. Thus, the time complexity for the third loop can be expressed as \begin{align*} \sum_{j=0}^{m-1} c \cdot b[j] = c \cdot \sum_{j=0}^{m-1} b[j]. \end{align*} Since the ...

0

Let $T(n)=U(\log n)$, then $U(\log n)=U(\log n-\log\log n)+\log\log n$. Let $V(x)=U(x)-x$, then $V(\log n)=V(\log n-\log\log n)=\text{ constant}$

0

There is a procedure to enumerate $\{ x : C(x) \lt \vert x \vert \}$, the set of all strings with descriptions shorter than themselves: evaluate every description (in parallel) to see what string it describes, and output that string if it is longer than its description. One way to do this is on time step $t = 2^k \cdot (2 \cdot x + 1)$, spend a unit of time ...

0

In general APX-hardness of $A$ will not immediately imply APX-hardness of $B$. Nevertheless, the implication holds if you strengthen the conditions of the reduction. If the reduction is approximation reserving, i.e. an approximation solution to $B$ corresponds to an approximation solution to $A$ when the reduction is applied, the implication still holds. The ...

1

The upper O-bound is trivial. To establish the lower bound, consider the following limit and apply L Hospital rule repeatedly $$\lim_{x\to\infty}\frac{\lg^{k}2x}{\lg^{k}x}$$ Note that $$\dfrac{d}{dx}\left(\lg2x\right) =\dfrac{d}{dx}\left(\lg x\right)$$

0

I now think that the problem is in fact trivially NP-complete. Whether there is a Hamiltonian path / cycle in a cubic graph (or, in the oriented case, a graph in which each vertex is adjacent to at most three arcs) is known to be NP-complete and can be reduced immediately to the problem at hand and its variants (whether there is a complete trail / circuit): ...

0

The for language is much simpler and is able to express all primitive recursive functions : You can have as many variables (a,b,c,...) as you want that contains a natural integer. The first variables are usually used as input (all other variable are initialised to 0) and the first variable can be used also as the output. Operations : incr a : to ...

1

Where $A, B$ and are complexity classes of languages (or problems), and $X$ is a set (/language), $A^X$ denotes the complexity class of languages accepted by Turing machines (TMs) conforming to the criteria of $A$ (e.g. log space, deterministic polynomial time), each TM augmented with the ability to use $X$ as an oracle: the machine can ask a single step ...

1

The Big-O time complexity is not affected if accessing a single entry is $O(1)$ (which would not be the case for array stored in one-dimensional singly-linked lists, for example). Regarding the constant hidden in the big O, opton 1 might be best because it improves cache performance on typical CPUs of today. So you are right if you consider 4 as correct ...

1

Let $x_1, x_2, \ldots, x_m$ be an instance of the NP-complete PARTITION problem. We will construct an instance of the optimization problem proposed here (converted to a decision problem) that encodes PARTITION. Let $A = \{a_1, a_2, \dots, a_{2m}\}$. We take $n=1$ so that there is only a single partition of $A$ consisting of $A$ itself. Let $c(a_i) = x_i$ ...

0

Your mistake is in the line where you have written $\delta + |\mathbb P(t(X) = 0) - \mathbb P(t(Y) = 0)| \le \textrm{dist}(X,Y)$. By the definition of statistical distance, your bound here is actually $2\textrm{dist}(X,Y)$. In fact, the expression you're trying to show is $0$ can actually also be $\textrm{dist}(X,Y)$, if $G_<\cup G_>=A$.

0

In your first question let $d=j-i$; then $$\sum_{i=1}^{k-1}\sum_{j=i+1}^k\frac2{j-i+1}=\sum_{i=1}^{k-1}\sum_{d=1}^{k-i}\frac2{d+1}\;.$$ Now let $\ell=k-i$, and note that as $i$ runs from $1$ up to $k-1$, $\ell$ runs from $k-1$ down to $i$. Thus, $$\sum_{i=1}^{k-1}\sum_{d=1}^{k-i}\frac2{d+1}=\sum_{\ell=1}^{k-1}\sum_{d=1}^\ell\frac2{d+1}\;.$$ This last ...

0

Just a wild guess, but it probably means what it says: the length of a bitstring encoding (in some reasonable manner) the parameters $l$, $u$, $b$ and $w$. That's because, presumably, the algorithm needs to at least read those parameters from it input, and that's going to take at least $O(k)$ time, where $k$ is the length of the input string encoding them. ...

1

In principal, they can be anything - the definition is purely abstract: a decision problem $X$ is in $NP$ if there is a polynomial-time function $V$ such that if $x\in X$, then $V(x, y)=1$ for some polysized $y$, and if $x\not\in X$, then $V(x, y)=0$ for every $y$. In practice, and more informally, the idea is that a decision problem $X$ is in $NP$ if it ...

0

One way to show that the theory of ordered divisible Abelian groups is complete is to prove that it is $\kappa$-categorical for some (and therefore all) uncountable $\kappa$. This is not particularly difficult, since any model can be viewed as an ordered vector space over the rationals.

0

If every $N$ requires to run a procedure that "builds" an algorithm in time $2^N$, then to execute the algorithm in time $N^3$, the complete task has exponential complexity. You may not assume that the algorithm for any $N$ is available at no cost, as this would require infinite precomputation and storage. Note that this discussion has nothing to do with ...

1

The key idea is that because the probability of error is less than one half you can decrease that probability further by repeatedly running the algorithm a polynomial number of times and accepting the majority result. For example, using the standard definition of $BPP$ which has a 1/3 probability of error, if you wanted a 99% probability of getting a ...

0

This is quite a well-traveled topic. You are struggling (it seems) to implement the Graham scan algorithm correctly. This is well-described in a number of locations, some including code. I will cite my own, associated with Computational Geometry in C: link here.                     (Image from Discrete ...

1

IF $L$ is a CFL, the Pumping Lemma for CFLs tells us that for some integer $n \ge 1$, if $s \in L$ and $|s| \ge n$, then $s$ can be written as $s = uvwxy$ where $|vwx| \le n$, $v\neq \varepsilon$ or $x \neq \varepsilon$, and for all $k\ge 0, uv^kwx^ky \in L$. If some $s\in L$ has length $n \le |s| < 2n$, then $L$ is infinite: for some $u,v,w,x,y$ ...

0

$T(3^k) = \mathcal{O}(1)\cdot (2^k - 1) + T(1)\cdot 2^k = \mathcal{O}(1) \cdot 2^k.$ Thus $$T(n) = \mathcal{O}(1)\cdot 2^{\log_3{n}} = \mathcal{O}(1)\cdot 2^{\frac{\ln{n}}{\ln{3}}} = \mathcal{O}(1)\cdot e^{\frac{\ln{n}}{\ln{3}}\cdot \ln{2}} = \mathcal{O}(1)\cdot \left(e^{\ln{n}}\right)^{\frac{\ln{2}}{\ln{3}}} = \mathcal{O}(n^{\frac{\ln{2}}{\ln{3}}})$$

0

It goes from (1) to (2), then from (2) to (3). If you want to bypass (2), you can do this: (1) is $\begin{array}\\ \sum_{j=1}^{k-1} (jn+n) &=\sum_{j=1}^{k-1} (j+1)n\\ &=n\sum_{j=1}^{k-1} (j+1)\\ &=n\sum_{j=2}^{k} j\\ &=n\left(\frac{k(k+1)}{2}-1 \right)\\ &<nk^2\\ &=O(nk^2)\\ \end{array}$

0

Here is an example of a problem that is much easier using Newton interpolation than Lagrange interpolation. Let $p(x)$ be the unique polynomial of degree $n$ such that $$p(k) = 3^k, 0 \le k \le n.$$ What is $p(n + 1)$?

0

Lagrange method is mostly a theoretical tool used for proving theorems. Not only it is not very efficient when a new point is added (which requires computing the polynomial again, from scratch), it is also numerically unstable. Therefore, Newton's method is usually used. However, there is a variation of the Lagrange interpolation, which is numerically ...

0

The theory $T_{dlo}$ of dense linear orders without endpoints is complete: for every sentence $S$ of the language $\{<\}$, either $T_{dlo}\vdash S$ or $T_{dlo}\vdash \neg S$. In fact, $T_{dlo}$ admits elimination of quantifiers: for every sentence $\varphi$ of the theory there is an open formula $\psi$ such that $T_{dlo}\vdash \varphi \leftrightarrow ... 2 Frankly, Lagrange interpolation is mostly just useful for theory. Actually computing with it requires huge numbers and catastrophic cancellations. In floating point arithmetic this is very bad. It does have some small advantages: for instance, the Lagrange approach amounts to diagonalizing the problem of finding the coefficients, so it takes only linear time ... 1 Here are two differences: Lagrange's form is more efficient when you have to interpolate several data sets on the same data points. Newton's form is more efficient when you have to interpolate data incrementally. 0 There are$2^n$integer of$n$bits, and computing one sum is a linear-time operation. Hence for the whole procedure, in the worst case $$O(n2^n).$$ This isn't polynomial. Indeed, for any degree$d$, you can find a value of$n>2d\$ such that $$n^d<2^n,(n+1)^d<2^{n+1},(n+2)^d<2^{n+2}\cdots,$$ as the ratio ...

1

Proof by Contradiction: Let's assume that there exists a longest word w' in Language L. And assume that there is an arbitrary alphabet a of length 1 in language L. Then the length of the word aw' = |w'| + 1 , but it is not possible to get the value of length aw' because the length of the longest word in an infinite language cannot be mapped to a countably ...

Top 50 recent answers are included