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
3answers
446 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
411 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
172 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
29 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
584 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
146 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
784 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
808 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
413 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
112 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
199 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
510 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
310 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
249 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
422 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
140 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 ...
0
votes
2answers
88 views

Triples algorithm complexity

This not optimal algorithm count the number of distinct triples $(i, j, k)$ such that $a[i] + a[j] + a[k] = 0$. ...
2
votes
1answer
205 views

Better compression for a positive DNF than via BDD

I am experimenting with compressing positive disjunctive normal form (DNF). When I use binary decision diagrams (BDDs) related algorithms I don't get very good results. For example the algorithms ...
9
votes
1answer
1k views

What is the significance of the graph isomorphism problem?

It seems that graph isomorphism is an overwhelmingly interesting problem, particularly computationally. Why is that? What are the (theoretical and practical) implication of the existence of an ...
0
votes
1answer
186 views

DTIME and time hierarchy theorem

we know that $\mathrm{DTIME}\left(o\left(\frac{f(n)}{\log(f(n))}\right)\right)$ is a subset of $\mathrm{DTIME}(f(n))$ but what can we say about $\mathrm{DTIME}{ \left(o\left(\frac{f(n)}{ (\log f(n) ...
6
votes
1answer
316 views

Complexity of finite group isomorphism problem

Consider the next decision problem: Given two finite groups represented by their multiplicity table, determine if they are isomorphic or not. Clearly, this problem belongs to NP since given a witness ...
0
votes
3answers
342 views

O-notation property - sum of the first n powers growth

I read here that in the tenth property: http://www.cs.auckland.ac.nz/~jmor159/PLDS210/latex/complexity.pdf The sum of the first $nr^{th}$ powers grows as the $(r+1)^{th}$ power This is not very ...
2
votes
2answers
126 views

Solovay Randomness

Say that an $x\in 2^{\omega}$ is Solovay random if for all computably enumerable collections of intervals $\{I_n\}$ such that $\sum_n\mu(I_n)<\infty$, then $x\in I_n$ for at most finitely many $n$. ...
2
votes
2answers
160 views

Can weight-restricted versions of monotone 2-SAT be decided in polynomial time?

I'm trying to answer a question from one of past test, The question is to decide if the following language is $\mathrm{P}$ (can be decided in a polynomial time) or $\mathrm{NPC}$ (can be decided by ...
1
vote
2answers
136 views

How can the following language be determined in polynomial time

I'd love your help with understanding why the following is decidable and can be determinate in polynomial time ($L \in P$). $L=\{(\langle M \rangle,w)|M$ is a Turing machine with Q states and one ...
8
votes
1answer
768 views

Why does Strassen's algorithm work for $2\times 2$ matrices only when the number of multiplications is $7$?

I have been reading Introduction to Algorithms by Cormen. Before explaining Strassen algorithm the book says this: Strassen’s algorithm is not at all obvious. (This might be the biggest ...
9
votes
0answers
520 views

Is there a theory that combines category theory/abstract algebra and computational complexity?

Category theory and abstract algebra deal with the way functions can be combined with other functions. Complexity theory deals with how hard a function is to compute. It's weird to me that I haven't ...
2
votes
3answers
450 views

Factoring extremely large integers.

The question is about factoring extremely large integers but you can have a look at this question to see the context if it helps. Please note that I am not very familiar with mathematical notation so ...
2
votes
0answers
120 views

matrix construction

Given any matrix $A$, can one construct a matrix $B$ such that $B$ is nonnegative and the spectral radius of $B$ is strictly less than 1 the determinant of $A$ is equal to the first entry of $B^*$ ...
6
votes
2answers
857 views

Time complexity to calculate a digit in a decimal

As we know, it is quiet fast to calculate any digit in a rational number. For example, if I'm given 1/7 (0.142857 142857 ...) and any integer K, I could easily return the Kth digit of 1/7, by doing a ...
1
vote
2answers
340 views

Approximating next prime number

Suppose that there is a prime number. Now I want to approximate the next prime number. (It does not have to be exact.) What would be the time-efficient way to do this? Edit: what happens if we limit ...
2
votes
0answers
134 views

reducing #P-complete problem to NP problem

What would be the consequence and meaning of existence of polynomial reduction of #P-complete problem into NP problem (not NP-complete problem)?
0
votes
1answer
73 views

complexity for $f(x)=n!$ and O($2^n$)

Suppose that algorithm has O($n!$). We all know that $n!$ should be smaller than $2^{2^n}$, but bigger than $2^n$. So, will O($n!$) be in EXPTIME (EXP)? Will we able to write O($n!$) as O($2^n$)?
3
votes
1answer
675 views

What is so wrong with polynomial hierarchy collapsing

Many computational complexity researchers believe that finite-level collapse of polynomial hierarchy is unlikely. Why do they believe like this?
4
votes
1answer
90 views

How do we distinguish NP-complete problems from other NP problems?

I just learned that when we have a polynomial algorithm for NP-complete problems, it is possible to use that algorithm to solve all NP problems. So, the question is how we then distinguish ...
2
votes
2answers
163 views

NP-completeness and NP problems

Suppose that someone found a polynomial algorithm for a NP-complete decision problem. Would this mean that we can modify the algorithm a bit and use it for solving the problems that are in NP, but not ...
1
vote
3answers
152 views

Time Complexity of $T(n)=T(n-2)+\frac{1}{\log(n)}$

Solve $T(n)=T(n-2)+\frac{1}{\log(n)}$ for $T(n)$. I am getting the answer as $O(n)$ by treating $1/\log(n)$ as $O(1)$. The recursive call tree of this is a lop-sided tree of height $n$. Hence, ...
1
vote
2answers
1k views

Is there a winning strategy for Scrabble?

I am sure many of us are addicted to the popular Facebook app: Words with Friends, which is basically an online version of Scrabble. In Playing Games with Algorithms:Algorithmic Combinatorial Game ...
10
votes
1answer
305 views

How can I intuit the role of the central limit theorem in breaking the curse of dimensionality for Monte Carlo integration

I would like to more intuitively understand where the power of Monte Carlo integration comes from for large-dimensional domains of integration. Other questions on this site have referenced the proof ...
2
votes
2answers
142 views

Sum set fixpoint, how many iterations?

I want to approach linear equations of the following form over the integers $\mathbb{Z}$: $$x_1 + \cdots + x_n = 0.$$ I stepped over the sum set, which is defined as follows: $$S + T = \{ x + y ...