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)

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
274 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
84 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 ...
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 ...
4
votes
1answer
66 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) = ...
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
189 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
411 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 ...
3
votes
2answers
265 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
341 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 ...
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
191 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
455 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
412 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 ...
5
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
46 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} ...
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} \\ ...
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, ...
2
votes
1answer
590 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
169 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 ...
0
votes
1answer
36 views

Complexity class, logarithms

I'm trying to show that $$\log_{a}(n) \in \theta(\log_{b}(n))$$ with $a,b > 0$ To prove it, I use the 'limit' theorem : $$g \in \theta(f) \Leftrightarrow \lim_{n \to +\infty} \frac{g(n)}{f(n)}=c$$ ...
1
vote
3answers
51 views

Computational complexity proof

I would like to know how to prove the following: $2^n \in O(n!)$ I know that I have to show that for a constant C, we have $2^n \leq C*n!$ Right?
0
votes
2answers
147 views

Find the rate of growth for $\sum_{n=1}^N 1/n^p$ in term of big $O$ notation

Find the rate of growth for $$ \sum_{n=1}^N \frac{1}{n^p} $$ in term of big $O$ notation for the three cases $0 < p < 1$, $p=1$ and $p>1$. It seems the question can be approached by ...
1
vote
1answer
798 views

Finding maximum of array consisting of an exponential amount of positive integers

Consider an array of an exponential amount of positive integer numbers, let's say $$ x_1, x_2, \ldots, x_{2^k} $$ for some fixed positive integer $k$. The question is the following. What is the ...
6
votes
2answers
823 views

Computing nth term of fibonacci-like sequence for large n

Sum up to nth term of fibonacci sequence for very large n can be calculated in O($\log n$) time using the following approach: $$A = \begin{bmatrix} 1&1 \\\\1&0\end{bmatrix}^n$$ ...
-2
votes
1answer
420 views

Prove that every problem in P is reducible [duplicate]

Possible Duplicate: For two problems A and B, if A is in P, then A is reducible to B? Given two problems $A$ and $B$, if $A$ is in $\def\P{{\mathcal P}}\P$ then $A$ is reducible to $B$. ($A ...
1
vote
2answers
116 views

What's the relation between the non-convex sets and the hardness of ILP problems?

If some or all of the unknown variables are required to be integers, then the problem is called an integer programming (IP) or integer linear programming (ILP) problem. If understand ...
0
votes
0answers
200 views

Maximum number of truths in an optimized truth table.

I have a math-related question: I have a set of predicates that need to be evaluated. These predicates can have two kinds of operators; AND/OR. When such an expression is constructed my code builds ...
1
vote
2answers
516 views

Sorting Algorithm analysis on a list of 0 and 1 element.

I'm trying to understand the difference would it make if following sorting algorithms are given a set of binary inputs i.e. collection of 0 and 1's only. a) Heapsort b) Quicksort c) MergeSort d) ...
2
votes
1answer
316 views

Function problem vs. decision problem

Take the set $FP$ of number-theoretic functions that are computable in polynomial time. Let us restrict to those functions with range in $\{0,1\}$, $FP_{0,1}$. Is there any correspondence with ...
1
vote
1answer
258 views

Why Savitch's theorem doesn't prove that NL = L?

Savitch's theorem proves that PSPACE = NPSPACE. Why the same theorem doesn't prove that NL = L?
0
votes
2answers
425 views

Inverse of matrix with QR method

What is the complexity of finding the inverse of matrix by QR decomposition? A is a $n×n$ with full rank.
1
vote
1answer
160 views

Question about computational complexity of algorithm

I'm quite confused about something. *So I have an algorithm which takes as input $k!$ numbers, let's call them $x_1, x_2, \ldots, x_{k!}$. *Then, in the algorithm, a 'matrix' is defined: i.e. for ...
1
vote
2answers
141 views

Algorithmic Complexity of $i^2$

I am new to the Big O notation in regards to algorithm design. I have had some exposure to it but I am not sure how to find the algorithmic complexity of a given function for a summation. If someone ...