Questions tagged [computational-complexity]

Use for questions about the efficiency of a specific algorithm (the amount of resources, such as running time or memory, that it requires) or for questions about the efficiency of any algorithm solving a given problem.

2,336 questions
13 views

Prove $T(n) = 2T(n-1) \in \Theta(2^n)$ [on hold]

Not sure how to prove this since there's no cost associated with each recursion.
23 views

maximum eigenvalue across subsamples

I have an $N$-dimensional vector of data, say $X_{t}$, with $1 \leq t \leq T$. Of this vector $X_{t}$, I want to consider sub-vectors, say $X_{t}^{b}$, which are $m$-dimensional combinations of ...
25 views

Proving NP-completeness for a problem is a generalization of a known NP-complete problem

For example, the List Coloring Problem (LCP) is a generalization of Graph Coloring Problem (GCP). As known, given graph $G(V,E)$ and an integer $k \leq |V|$, the question that whether $G$ is $k$-...
29 views

NP-completeness of chromatic sum in list coloring problem with capacity constraints

I am trying to solve a problem that can be considered as minimizing the sum of colored numbers in a List Coloring Problem while satisfying some restricted constraints. In the List Coloring Problem (...
61 views

Is the complexity of $\binom{2n}{n} = O(2^n)$? [on hold]

How to find the complexity of $f(n)=\binom{2n}{n}$? We know that $f(n)=\binom{2n}{n} = \frac{(2n)!}{(n!)^2}$. Is this $O(n^2)$? What concerns me is $n!$
24 views

Why is $f(n) = Θ(g(n))$ where, $f(n) = n^4 - n^3$ and $g(n) = 16^{\log(n)}$

I saw an example that claims that: $f(n) = Θ(g(n))$ where, $f(n) = n^4 - n^3$ and $g(n) = 16^{\log(n)}$ I can understand how the polynomial f(n) is translated into $O(n^4)$ and that it also has a ...
9 views

pspace-complete definition variation with cubic space(theoretical)

i've been wondering: if we change the definition of a PSPACE-COMPLETE definition to the following: A language B will be called PSPACE-COMPLETE if: for each language A in PSPACE: $A \leq _{CS} B$ ...
45 views

Recommended Language(s) for Performing Arbitrary Precision Calculations on a PC

I would be grateful if someone could point me in the direction of a programming language (and also, where I may find good tutorials on it to teach myself) that can perform arbitrary bit-precision ...
37 views

How to see if a graph with two coloring has a monochromatic triangle?

Lets say you have an adjacency matrix version of K6 graph colored red or blue. How do you determine if there is a monochromatic triangle. For example, ...
35 views

100-cut problem graph theory [closed]

100-cut={G|G is undirected graph, and have a cut in size>=100} I'm guessing that 100-CUT is in p, because unlike MAX-CUT here we need a cut that greater than a constant number, but I cant think of an ...
24 views

Computational complexity of $x x^H$

Assume $x\in \mathbb{C}^{n\times n}$. What is the computational complexity (cost) of $x x^H$ where $H$ is the conjugate transpose? I know this gives a symmetric matrix and we can divide by $2$ the ...
21 views

What's the effect on other complexity classes if P=L?

Let's say theoretically we discover that the P complexity class (decision problems solvable by a polynomial time deterministic TM) is equal to the L complexity class (decision problems solvable by a ...
25 views

BPP(complexity) with binary form of number

For any language $L \subseteq \mathbb{B^{*}}$ we define language $L^{log}$ as set $\{\overline{a}\overline{b} | \overline{a} \in L, \, \overline{b} - \text{binary form of number}\,\, |\overline{a}|\}.$...
29 views

BPP (complexity)

For any language $L \subseteq \mathbb{B^{*}}$ we define language $2 \cdot L$ as set $\{2 \cdot \overline{a} | \overline{a} \in L\}$, where $2$ in binary form equals $10$,and $\cdot$ - is ...
23 views

Why is the following algorithm for K-CLIQUE not in NL?

It's known that K-CLIQUE is a NP-Complete problem. The question is, what am I missing in the following non-deterministic algorithm, which should decide the K-CLIQUE problem in O(logn) space. (It ...
30 views

59 views

A polynomial algorithm to determine whether a finite group is nilpotent

Does there exist a polynomial (in respect to the order of the group) algorithm that given a Cayley table of a finite group determines, whether a group is nilpotent or not? There do exist polynomial ...
31 views

Complexity of solving a linear equation system over $k[x]$

Let $k$ be a field and let $A \in k[x]^{m \times n}$ be a polynomial matrix whose entry with highest degree has degree $d$. Let $b \in k[x]^m$. What is known about the complexity of computing a ...
47 views

Sum of sqrt of eigenvalues without computing all eigenvalues

Let $A$ be a positive-definite matrix with eigenvalues $e_1, ..., e_n$. I want to compute $\sum\limits_{i=1}^{n} \sqrt{e_i}$ without calculating all eigenvalues first (or rather: with a method faster ...
13 views

ST-CON variation: is it also in NL?

Consider the following variation on the ST-CON decision problem: given a directed graph $G$, for every two different vertices $s$ and $t$, there is a directed path between $s$ and $t$. Intuitively, it ...
18 views

What is the lowest computational complexity of multiplying two non-square matrices?

Based on Wikipedia information, the computational complexity of multiplying two $n\times n$ matrices can be $\mathcal{O}(n^{2.37})$ using algorithms similar to Coppersmith–Winograd. I wonder what if ...