Computational complexity, a part of theoretical computer science.
1
vote
1answer
30 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
77 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
40 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
112 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
69 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
452 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 ...
1
vote
0answers
15 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) = ...
0
votes
0answers
25 views
what is the time Order for an special input to heapsort?
My homework question Is "Find the heap-sort execute time if the input array A be an increasing sorted array).
I thought about 2 hours on this problem but i really didn't find any difference in ...
2
votes
1answer
46 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 ...
5
votes
2answers
99 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
63 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 ...
1
vote
0answers
39 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
68 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
18 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
96 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 ...
0
votes
0answers
118 views
Solve recursion formula using Recursion Tree concept
I'm trying to figure out an important idea regarding solving Regression formulas / Recurrsion formulas using the Recursion Tree idea.
I will first write down the exercise and then I'll try to explain ...
0
votes
0answers
39 views
prove certification complexity?
How to prove that
$$ C_1(f) = \min\{k : f \text{ is a $k$-DNF}\} $$
and $$ C_0(f) = \min \{ k: f \text{ is a $k$-CNF}\} $$
fulfill
$$
C_1(f) = \max\{C(f,x):f(x)=1\}， \qquad ...
0
votes
0answers
22 views
Dynamical programming algortihm
I'm trying to apply the Dynamic Programming technique to 3-SAT. However, I'm a bit confused.
Say you have an expression like this
$(x_1 \vee x_2 \vee x_3)\wedge (x_1 \vee \neg x_2 \vee \neg x_3) ...
0
votes
2answers
55 views
what is the complexity and how to start
Every year, Prof Gupta assigns the instructors to various faculty committees. There
are n faculty members and c committees. Each committee member has submitted a list of
their prices for serving on ...
4
votes
1answer
58 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
30 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
100 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
170 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.
1
vote
0answers
10 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 ...
2
votes
2answers
134 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 ...
3
votes
0answers
184 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
182 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 ...
1
vote
1answer
113 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
53 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 ...
0
votes
0answers
32 views
Computing the minimum generating set for a $p$-group
This is a more specific form of the question "How do I find the minimum size of a generating set of a group?".
Is there a general rule which describes the minimum size of a generating set of a ...
2
votes
0answers
27 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
63 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 ...
4
votes
3answers
95 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
83 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
179 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 ...
3
votes
1answer
86 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
90 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
58 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
25 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
78 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 ...
1
vote
1answer
112 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
71 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
33 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
38 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
78 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} \\
...
0
votes
0answers
13 views
Computing a vector that two matrices jointly map to the negative orthant
I have two $n \times n$ matrices $A$ and $B$. I would like to find a vector $v \in \mathbb{R}^n$ satisfying: (1) $\min(Av, Bv) \le 0$ and (2) NOT $v \ge 0$, or decide that no such $v$ exists.
The ...
1
vote
0answers
25 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, ...
1
vote
1answer
87 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 ...
0
votes
0answers
97 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
22 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$$ ...
