Computational complexity, a part of theoretical computer science that deals with understanding how efficiently a problem can be solved.

learn more… | top users | synonyms (1)

1
vote
0answers
88 views

“Balancing” two infinities

Given these two computational complexities of 2 algorithms: $\exp(O(\sqrt{\log n \log \log n}))$ $O(\sqrt{\exp n} / \log{ \sqrt{ \exp n} })$ where I imagine the first one goes to infinity slower ...
5
votes
2answers
294 views

Is there a function that only generates primes?

The title sums it up: does there exist a "nice" injective function $f(n)$ such that $f(n)\in\mathbb P$ for all $n\in\mathbb N$? I'm having difficulty specifying exactly what I want "nice" to mean, ...
4
votes
3answers
147 views

How to find $(-64\mathrm{i}) ^{1/3}$?

How to find $$(-64\mathrm{i})^{\frac{1}{3}}$$ This is a complex variables question. I need help by show step by step. Thanks a lot.
15
votes
1answer
13k views

What is the time complexity of Euclid's Algorithm (Upper bound,Lower Bound and Average)?

I looked it up online in many sites but none give a clear answer. They all give a lot of complicated mathematical stuff which is not only hard for me to grasp but also irrelevant as I simply want to ...
1
vote
1answer
41 views

Why does it take maximum of $n/\log n$ digits to represent the number $2^n - 1$ in base of $n$?

Given the number $n$. Why does it take maximum of $\frac{n}{\log n}$ digits to represent the number $2^n - 1$ in base of $n$?
0
votes
1answer
1k views

How to prove perm-power is in P?

Let $\mathit{PERM\text{-}POWER} = \{ \langle p, q, t\rangle \mid p = q^t \}$ where $p$ and $q$ are permutations on $\{1, \ldots, k\}$ and $t$ is a binary integer. How do I prove that $\mathit{PERM\...
1
vote
0answers
80 views

Big Omega Proof Switch

Big omega definition: $f(x)=\Omega(g(x))$ if $f(x) \ge c g(x)$ Is it correct to switch it around to proof: $$g(x) \le c f(x)$$ I am afraid that moving the '$c$' to the other side may change the ...
1
vote
1answer
2k views

Proof that computing composition of permutations is in P

Consider the following problem: A permutation on the set ${1,…,k}$ is a one-to-one, onto function on this set. When $p$ is a permutation, $p^t$ means the composition of $p$ with itself $t$ times. ...
1
vote
1answer
47 views

Polynomial transform (P, NP)

There are problems A and B in NP. Problem A polynomially transforms to problem B. Suppose A is in P. Is it correct to state that this teaches us nothing new about problem B?
2
votes
1answer
141 views

Oracle turing machine

I am learning computational complexity and this is a question of my assignment that I have issues trying to solve/understand. An oracle Turing Machine M with oracle A is a Turing Machine with an ...
2
votes
1answer
123 views

IF a language L logspace reduces to SAT, does L

If a language L logspace reduces to SAT, does L also reduce to SAT in polynomial time?
1
vote
1answer
1k views

How to prove CYK algorithm has $O(n^3)$ running time

I have a final coming up in few days, and the professor mentioned the CYK algorithm. I want to be prepared for the final. I'm trying to find out how to prove the algorithm has worst case running time ...
2
votes
1answer
462 views

Complement of NP-Complete

If a language L is NP-complete, with respect to polynomial time reducibility, does L ≤ co-L in polynomial time?
1
vote
1answer
4k views

Algorithm to check whether a graph has no cycles

Let $G=(V,E)$ be an undirected graph. Design an algorithm which decides whether the graph contains a cycle and proove its correctness and determine its complexity in terms of $\mathcal{O}$-notation. ...
2
votes
0answers
36 views

complexity of time constructible function

In field of computational complexity there is a definition of time constructible function. As example, in any reasonable and general model, functions like $t_1(n) = n^2, t_2(n) = 2^n$, and $t_3(n) = ...
2
votes
1answer
75 views

Using the notation $m^{O(1)}$

$m^{O(1)}$ denotes the set of functions $\mathbb{N} \to \mathbb{N}$ which are polynomially bounded. (Is that what is usually means?) Now it used as follows: $$ f(m) \leq m^{O(1)}$$ To express that $...
6
votes
2answers
278 views

Time complexity - Why does doubling the speed given this improvement?

Hi I've been studying time complexity recently and I'm really confused about something I've come across. The problem Suppose we can solve a size n problem instance in 1 hour. If we double the ...
1
vote
1answer
83 views

Proof of NP-completness for the foll0wing

I have encountered a problem similar to Set Cover (and Maximum Coverage): We have several sets in a universe with $N$ elements. What is the maximum number of sets so that the number of elements found ...
2
votes
1answer
85 views

Computational complexity of unknotting problem?

The Wikipedia article on the unknotting problem says "a major unresolved challenge is to determine [...] whether the problem lies in the complexity class P". It mentions some work towards this result ...
0
votes
1answer
169 views

compute overlapping % of 2 parallel lines

I have two parallel line segments, say AB, CD. If I project the end points onto a common third parallel line, then I want to know the portion of overlap made by above 2 lines. I think I should use ...
1
vote
1answer
26 views

How to verify that $(x_1 + … + x_n)^2$ represents $MOD_3$

I have question about Computational Comlexity, the following statement can be found in $AC^0$ Circuits Cannot Compute PARITY. Each $n$-varibale polynomial over $\mathbb{Z}_3$ defines a function from $...
1
vote
2answers
135 views

Möbius function help

Given some large random integer k, how much longer would it take to determine the primality of k, then to calculate mobius(k), and how much longer would it take to factor k, then to calculate mobius(k)...
4
votes
1answer
67 views

Number of solutions $x_1x_2\dots x_k = n, x_i, n \in \mathbb{N}$

Here's a question I've been asked: Let $n\in \mathbb{N}$ and let $d_k(n)$ be the number of solutions of $$x_1\dots x_k = n, \hspace{5mm}x_i\in \mathbb{N}$$ I need to show $$d_k(n) = \sum_{d|n}d_{k-...
0
votes
1answer
44 views

Number of steps to eliminate all elements from an array, reducing by a decreasing fraction

Assume I have an array of $N$ (say $N$ very large) elements. I proceed removing $1/2$ of the elements then, from what remains, I remove $1/3$ of the elements, then, from what remains, i remove $1/4$ ...
4
votes
1answer
190 views

In terms of complexity, is there a quicker way of checking if a matrix is nonsingular than computing the determinant?

To repeat the question, let $A$ be a square matrix. We wish to determine if $A$ is nonsingular, that is, invertible. One way is compute its determinant and check if it is nonzero. However, if $A$ is ...
3
votes
1answer
413 views

contiguous sublists of a list with positive sum

Does anyone know of an algorithm that finds contiguous sublists of a list with positive sum? Preferably in O(n). I'm more interesting in the max length of those lists. Thank you in advance.
2
votes
0answers
19 views

On the computational complexity of plugging in numbers into general expressions to obtain special ones

There are many expressions, which can be considered straight generalizations of others. I'm motivated by values of integral expressions specifically, for example there is $$\int_0^\infty e^{-a x^2}...
3
votes
2answers
266 views

solving a non-standard recurrence relation in asymptotic terms (using Big O notation)

Looking at the following recurrence relation: $$ T(n)= T(n-x)+T(x)+O(\min(x,n-x)) $$ $$ T(1)=1 $$ where $x$ can devide our problem in any proportion (may vary from call to call -- not a constant ...
9
votes
2answers
2k views

If an unary language exists in NPC then P=NP

I've a question regarding a theorem in Complexity Theory. It is said that if there exists an unary language in NPC then P=NP e.g if {1}* in NPC then the above is correct. It means that there exists ...
2
votes
1answer
345 views

approximation of binomial coefficient sum

I would like to find some approximation or upper & lower bounds on the next simple expression: \begin{align} \sum_{i = 0}^{k} \binom{h}{i} \qquad h \geq k \end{align} But I need this ...
4
votes
1answer
1k views

Baker-Gill-Solovay theorem

I have been trying to understand the proof of Baker-Gill-Solovay theorem as described in Complexity Theory: Modern Approach. I think I do understand most of it, but what troubles me is that let's say ...
1
vote
2answers
63 views

What is this number $k$?

I'm reading A first Course on Logic, (Hedman). An algorithm is said to be polynomial-time if there is some number $k$ so that, given any input of size n, the algorithm reaches it's conclusion ...
2
votes
0answers
51 views

How would you write this sentence

I'm writing a short document about an integer programming (IP) problem instance. I've mentioned that IP is known to be NP-Hard, but that being NP-Hard doesn't automatically qualify this particular ...
0
votes
1answer
143 views

Prove that the little-o definition doesn't hold for two function (f and g)

I need your help with the following statement: Show there exist two function $f(n), g(n)$ such that meet the following definition: $g(n) = O(f(n))$ and $f(n) \ne O(g(n))$ But don't meet the little-...
5
votes
3answers
161 views

What would be complexity of computing $3^{n^n}$?

Just curious, what would be the computational complexity of computing $3^{n^n}$? I am not sure what it would be like.
0
votes
2answers
240 views

Some Big-O complexity definition proofs

I'm trying to prove (by definition) the following but to no avail: $n^{n/2} \ne O(3^{n/2}) $ $n! \ne O(3^n)$ $(n-b)^a = \Theta(n^a)$ $a,b $ are both constants whereas $a > 0 $ and $b$ ...
0
votes
2answers
3k views

Little-o proof by definition

I'm trying to figure out how to prove the following but to no avail. Given the following functions : $f(n) = n^3 -4n$ $g(n) = 5n^2 + 3n$ I have to show that $g(n) = o(f(n))$ by definition, that ...
4
votes
1answer
192 views

NP-complete Problems

It seems from reading that problems are determined to be NP-complete if they can be shown to be equivalent to another NP-complete problem. However, I wonder how the "original" NP-complete problem was ...
1
vote
3answers
463 views

Order of magnitudes comparasions

I have a list of order of magnitudes I want to compare. My only idea is using calculus methods (limits , integral, etc...) to assert the functions relation. I need your help with the following. I ...
0
votes
3answers
88 views

Big-O compared to a new Operator

I'm trying to figure out a new operator compared to the Big O. Suppose we have two positive functions, $f(n)$ and $g(n)$ then we say that $f(n) = O^*(g(n))$ if there exists a constant $ c > 0 $ ...
1
vote
1answer
33 views

Weird BigOmega statement - Totality

I've just encountered a weird statement regarding the BigOmega operator. I should prove that the BigOmega operator isn't totally ordered. As a prove hint, I should show that there are two functions, ...
0
votes
1answer
414 views

Difficulty proving / finding witnesses for the following Functions (Big O and Big Ω and $\Theta)

I have left with some functions I can't find witenesses for proving Big O and Big Ω and Big $\Theta$ relations. Notice that I should prove the following using the defintion and not any complex ...
6
votes
1answer
2k views

Orders of Growth between Polynomial and Exponential

What is known in contemporary mathematics about orders of growth for functions that exceed any degree polynomial, but fall short of exponential? This is a subject for which I've found little ...
1
vote
1answer
174 views

Understanding of working of Turing Machine for $\{0^k1^k\}$

I try to learn Computation Complexity by Sipser's textbook "Introduction to the Theory of Computation". The problem is I have a lack in understanding how Turing Machine is working. Example from the ...
0
votes
0answers
47 views

How can i count the number of flops of the following expression?

lets say, after Cholesky factorization, at some point in my solution I get this: $L_{11}*L_{11}^T=A$, $L_{11}*L_{21}^T=u$, $L_{21}*L_{11}=u^T$, and $L_{21}*L_{21}^T=a$ So, $a$ is a scalar, $u$ and $...
1
vote
1answer
61 views

How do you prove that a sum of functions is in Omega of one of the functions?

I have to prove the following statement: $$ f(n) + g(n) \in \Omega(f(n)) $$ I am not sure what to do. Can I use this somehow? $$ f(n) \in \Omega(g(n)) : \iff 0 \le lim_{n \rightarrow \infty} \frac{f(...
0
votes
1answer
97 views

How can I do this kind of Cholesky decomposition?

$B_{(n+1)(n+1)}$ = $ \begin{bmatrix} A & u \\ u^T & 1 \\ \end{bmatrix}$ = $\begin{bmatrix} L_{11} & 0 \\ L_{21} & l_{22} \\ \end{...
1
vote
0answers
30 views

how to show cholesky decomposition complexity? [duplicate]

Possible Duplicate: How to calculate the cost of Cholesky decomposition? so far i see that for matrix A = L*L^T : (A = a1, a2, a3, a4 matrix) FOR lower triangular matrix L = l11, 0, L21, L22 (...
2
votes
1answer
597 views

Polynomial complexity algorithm of partition problem with sets of equal size

Partition problem is well known ( http://en.wikipedia.org/wiki/Partition_problem ). Let's add an additional condition: sizes of both sets should be equal. Is there a pseudo-polynomial solution to ...
1
vote
0answers
170 views

Does there exist a group (finitely presented) such that the isomorphism problem for the group and the trivial group is undecidable?

It is well known that the isomorphism problem for finitely presented groups is unsolvable. That is to say that if $G$ and $G'$are both fp- groups, then in general it is impossible to provide an ...