Computational complexity, a part of theoretical computer science.
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$$ ...
1
vote
3answers
43 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
47 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 ...
0
votes
1answer
59 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 ...
5
votes
2answers
173 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
123 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
47 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
81 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
90 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
110 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
60 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
108 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
89 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
102 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
48 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
102 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 ...
5
votes
1answer
233 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
145 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) ...
5
votes
1answer
108 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
109 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
86 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
104 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
94 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 ...
4
votes
1answer
245 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 et al. Before explaining Strassen algorithm the book says this:
Strassen’s algorithm is not at all obvious. (This might be the biggest ...
4
votes
0answers
142 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
212 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 ...
0
votes
0answers
121 views
On the complexity of $n!$
The reference below shows if $n!$ is ultimately hard, then $P_{\mathbb{C}} \ne NP_{\mathbb{C}}$. Is there any implication about the case if $n!$ is easy?
On the intractability of Hilbert's ...
0
votes
0answers
77 views
A polynomial reduction which involves computing $n!$
I want to do a polynomial reduction from problem $A$ to problem $B$. Let $n$ denote the input size of $A$. Is the reduction still polynomial if my reduction algorithm computes the value $n!$ for some ...
2
votes
0answers
92 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^*$ ...
4
votes
2answers
202 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
227 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
100 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
58 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$)?
1
vote
1answer
88 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?
0
votes
0answers
76 views
Finding the largest subgraph that has hamiltonian path [closed]
Is finding the largest subgraph (of a graph) that has hamiltonian path NP-complete?
This may be restated as the following: is finding the largest line path of a graph NP-complete?
Also, is finding ...
4
votes
1answer
79 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
92 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
84 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
251 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
206 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
132 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 ...
1
vote
1answer
104 views
Vertex Cover - upper bound
A few definitions:
$\mathsf{VC} = \{ (G,k) \mid \text{There exists a vertex cover of size $k$ in $G$}\}$
$\mathsf{VC_{LOG}} = \{ G \mid \text{There exists a vertex cover of size $\leq \log |V|$ in ...
0
votes
1answer
106 views
How do you prove that a game is undecidable?
I'm studying a game that is played on a graph, there are two teams, attackers and defenders. The attackers are attempting to capture the King by occupying all of his neighbours, the defenders are ...
1
vote
1answer
76 views
VP Definition: Why polynomial bound on the degree?
The complexity class $\mathbf{VP}$ (Valiant P) is defined to be the class of all polynomials of polynomially bounded degree which can be realized by an arithmetic circuit family with polynomially ...
5
votes
1answer
177 views
Is there an efficient algorithm to compute a minimal polynomial for the root of a polynomial with algebraic coefficients?
An algebraic number is defined as a root of a polynomial with rational coefficients.
It is known that every algebraic number $\alpha$ has a unique minimal polynomial, the monic polynomial with ...
1
vote
1answer
222 views
Worst case of Heapify is $\Omega(n \lg n)$
Worst case of Heapify is $\Omega(n \lg n)$
I know that Heapify is $\Theta(\lg n)$, but I don't know if $\Omega(n \lg n)$ is equivalent.
Thanks.
1
vote
1answer
101 views
Sum in tree nodes - algorithm
I've got one very hard problem.
Given a tree with nodes with integers. We need to find the largest sum of label values for a set of nodes which does not include any adjacent pair of nodes.
...
0
votes
0answers
27 views
Fast approximate construction of orthogonal system
Assuming I have $d+1\in\mathbb{R}^d$ points that are not unfortunately chosen (in which case I can just resample, correct me if I $d$ points are enough), then these should span the whole space.
What ...
0
votes
0answers
125 views
Solving a problem by reduction
I am aware that for a problem to be considered NP-Hard, any problem in NP must be reduceable to your problem (problem which you are trying to prove is NP-Hard).
Let's assume that you have proven that ...
