Tag Info

New answers tagged computational-complexity

0

This can be done in polynomial time for any dimension. Assume WLOG the boxes are distinct. Form a graph from the "fits inside" relation. This is a directed acyclic graph. Each group is a path in this graph, and we want to partition the vertices into as few paths as possible. This is exactly the problem of minimum path cover in directed acyclic graph. The ...

0

As it turns out, several enterprising gentlemen discussing the original problem found a provably optimal $\mathcal{O}\left( n^2\right)$ algorithm, which can be generalized to the $p$-dimensional case, $p \geq 3$ via Dilworth's theorem. Hence this resolves question 2. The question about whether this box-grouping problem or others similar to it have a formal ...

0

Through out the research in the latest years many people have introduced new classes of problems, in other words they tried to categorized problems considering many aspects of computation. Not only the running time as in $\mathrm{P}$ vs $\mathrm{NP}$. Or other models of calculation such as Randomized Turing Machines or even Quantum. One particular class of ...

0

Well, if $f(n)=O(n^2)$ then $f(n)=O(n^2\log n)$ by definition, so you aren't wrong, there is just a better bound. The trick is knowing that $\sum_{i=0}^\infty \frac{1}{2^i}=2$. So $\sum_{i=0}^{\log n} \frac{1}{2^j} = O(1)$.

0

Let's transform the expression under the logarithmic function: $$10 \cdot \log(n^{30} + 30) + 2 = 10 \cdot \log(n^{30}\cdot(1 + \frac {30} {n^{30}})) + 2 = 10\cdot\log(n^{30}) + 10\cdot\log(1+\frac {30} {n^{30}}) + 2$$ And you see the dominant term now, right?

4

The post Reasons to believe from Scott Aaronson's blog states... ...ten arguments for believing P!=NP: arguments that are pretty much obvious to those who have thought seriously about the question, but that (with few exceptions) seem never to be laid out explicitly for those who haven’t. You’re welcome to believe P=NP if you choose. My job is to make you ...

0

Note that $(a \mid b)^{*}$ means $\{\varepsilon, a, b, aa, bb, ab, ba, \dots \}$, so $(bb \mid b)^{*} = \{\varepsilon, b, bb, bbb, \dots \} = b^{*}$. That leads to $$R = (a \mid b) (bb \mid b)^{*} = (a \mid b) b^{*}$$ So the language created by $R$ is $L(R) = \{ a^lb^k \mid k \in \mathbb{N}_0, 0 \leq l \leq 1\}$. Converting your NFA to an equivalent DFA ...

0

$O(f (n)) = O(g (n))$ is a shortcut for "every function in the set $O (f (n))$ is also a member of the set $O(g (n))$". Now if you proved that f (n) is in $O(g (n))$, you can show quite easily that every element of the set $O (f (n))$ is also a member of the set $O(g (n))$. You can't just take the logarithm on both sides. That might prove that $\log f (n)$ ...

0

Well, I will try to answer the questions that I think you are asking. If the P=NP? question is solved positively, then the answer should be (quite possibly) in the form of an algorithm that solves an NP-hard problem in polynomial time. NP-hard problems are those problems that are at least as hard (computationally speaking) as any problem in the class NP, so ...

0

Actually, you don't even need logarithms. Consider $f(n) = 2n$ and $g(n) = n$. Then, $2^{f(n)} = 2^{2n} = 4^n$ but $2^{g(n)} = 2^n$. Can you show that $2^{f(n)}$ is not $O(2^{g(n)})$?

2

It's easy to see that computing $\alpha(G) + \omega(G)$ (for general $G$) is equivalent to computing $\alpha(G)$: given any graph $G$, construct $G'$ as the disjoint union of $G$ with $K_n$ where $n$ is the number of vertices of $G$. Then we easily have $\omega(G') = n$ and $\alpha(G') = 1 + \alpha(G)$, so if you could compute $\alpha(G') + \omega(G')$... ...

0

Use binary search algorithm to find such a $j$ for which $a_{j-1}>a_{j}$ and $a_{j+1}>a_{j}$. Then $j=k$ and $a_j$ is minimum element of the sequence. If $a_{i-1}>a_{i}>a_{i+1}$ you know that $i<k$. If $a_{i-1}<a_{i}<a_{i+1}$ you know that $i>k$. You can adapt binary search algorithm to solve this problem.

2

Take $n=m^{2^k}$, then $$T(m^{2^{k+1}})=T(m^{2^k})+1$$ and if $S_m(k)=T(m^{2^k})$, then $S_m(k)=k+S_m(0)$. Hence $$T(n)=\log_2(\log n)+c.$$

1

For a log-polynomial expression $\sum a_kn^{i_k}\log^{j_k}(n)$, take the highest power of $n$ and in case of equality take the highest power of the $\log$. In your case, the dominant term is $n^6$, and $$\frac{g(n)}{n^6}=1-\frac{9\log^2 n}n-\frac{16}{n^5}-\frac5{n^3}.$$ The limit is clearly $1$. Also note that the second term has a maximum for $n=e^2$ so ...

2

there's a faster way: if $$\lim_{x\to \infty}\frac{f(x)}{g(x)}\in\mathbb{R}/\{0\}$$ then $$f(n)=\Theta(g(n))$$ And this is easy to prove

0

You need to show that for all $k$, there exists $c_k$ such that $\log n \leq c_kn^{1/k}$. So, fix $k \in \mathbb{R}^+$ \begin{align} \log n \leq c_kn^{1/k} &\Leftrightarrow c_k \geq \frac{\log{n}}{n^{1/k}}. \end{align} Let us find the maximum value of $\frac{\log n}{n^{1/k}}$. Taking the derivative, we get \frac{d}{dx}\frac{\log ...

1

One way is calculating limit: $$\lim_{x \to \infty} \frac{\log x}{x^{\frac{1}{k}}}$$ You can use for example L'Hospital rule: $$\lim_{x \to \infty} \frac{\log x}{x^{\frac{1}{k}}}=\lim_{x \to \infty} \frac{\frac{1}{x}}{\frac{1}{k}x^{\frac{1}{k}-1}}=\lim_{x \to \infty} \frac{k}{x^{\frac{1}{k}}}=0$$ So for $n \in \mathbb{N}$: $$\lim_{x \to \infty} ... 1 There are multiple possible ways to define it, but on reasonable way to define it is like so: O(g(n)) is the set of all functions f:\mathbb{R}\to\mathbb R where there exist k, N\in\mathbb R such that whenever n>N, f(n)<k g(n). (i.e. f is eventually bounded above by g) That means O(n) is the set of functions that are bounded above by ... 13 Since \Bbb R is a set, we know that \Bbb{R\times R} is a set, so \mathcal P(\mathbb{R\times R}) is a set. Therefore the collection of all functions from \Bbb R to itself is a set. In particular any definable subcollection of a set is a set. For example, all the functions which are O(n) or otherwise. 0 If you are thinking of functions f:\mathbb{N}\to\mathbb{R}, you have a proper set. 0 This all derives from the fact that if f_2 \subset f_1, i.e. function of a lower order, we can always find some n_0 >n and constant a s.t. f_1 + f_2 < f_1 +a f_1 = (1+a)f_1 = O(f_1) 1 Your calculations are correct, but I think it's the phrasing that's confused, order doesn't matter here in quite the way you seem to think it does. (If I'm interpreting your statement correctly.) Carefully phrased, you've found: Because$$\lim \frac{n^2}{n^3} = 0$$we can say that n^2 is O(n^3) (it's also O(n^2)). Because$$\lim\frac{n^3}{n^2} ...

-1

I think that the question should be refined, since one obvious answer to your question is: The set of even numbers, and The algorithm that, with an even number $n$ as input, only outputs "PRIME" when $n = 2$, outputting "COMPOSITE" otherwise. Of course, this is not the answer you are looking for. However, how can you modify the question so its answered ...

2

It's true that the plane is continuous, but the Voronoi diagram consists of finitely many polygons. Moreover, the vertices of those polygons have coordinates that are rational functions of the original set of points. So the computational complexity of Voronoi-diagram computation is well-defined; you just have to be in a computational setting where you can do ...

2

To address your first question, the ordinary discrete notion of NP-hard indeed does not apply to continuous problems such as this one. On the other hand, there is a theory of computational complexity for problems with continuous data: look up Blum-Shub-Smale machines.

1

If speaking of an algorithm, saying a specific algorithm is "O of n squared" is commonly used, especially in the vicinity of computer scientists.

1

I've usually head big oh of x but as long as your audience know what you're talking about it doesn't really matter too much, unless you're working with a function O it's not likely that anyone will mistake you. Unless you're working with little o as well. Little o doesn't seem to be used that often though so the chances for confusion should be pretty small.

1

Since the vertices in a clique are pairwise adjacent, the vertices in the clique must be assigned distinct colors. Thus, any proper coloring of the graph will require at least as many colors as the size of the largest clique in the graph. The difference between the chromatic number and its lower bound (the clique number) can be made arbitrarily large - ...

1

The answer to your first question is yes. A graph is perfect if the chromatic number of each induced subgraph is eqaul to the size of the largest cliqu in the subgraph. There is a large literature on these but, unfortunately, most graphs are not perfect On the other hand there are triangle-free graphs with arbitrarily large chromatic number, so nothing much ...

0

$log(n) \notin \Theta(log(n^n))$ You can prove this fairly easy. If you know how logarithms work, you can do the following: $log(n^n) = n.log(n)$ and that is obviously not in $\Theta(log(n))$ since it grows $n$-times as fast. $f(n) \in \Theta(g(n))$ if and only if $f(n) \in O(g(n))$ and $f(n) \in \Omega(g(n))$. But in this case $log(n) \notin ... 1 Definition of space-constructible functions goes like this: A function$f$is space-constructible if there is a TM that, on input$1^n$, uses$\Theta(f(n)$cells of the TM. There might be slightly different version of this definition, but the point is that you can prove that a function is space-constructible simply by constructing a multi-tape TM that ... 0 Yes, using the Fast Fourier Transform algorithm, you can do it in$O(n log_2 n)\$.

5

This is not really my answer. Being vastly ignorant on such matters, I asked Carl Pomerance who replied : Pintz, Steiger, and Szemeredi did this some time ago, and a paper of mine with Konyagin went further. This is all pre-AKS. My paper with Konyagin is #111 on my home page, and the PSS paper is referenced. Basically all you want are primes p with a ...

Top 50 recent answers are included