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.

0
votes
1answer
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.
0
votes
0answers
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 ...
1
vote
1answer
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$-...
1
vote
1answer
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 (...
1
vote
2answers
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!$
1
vote
1answer
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 ...
0
votes
0answers
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$ ...
1
vote
1answer
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 ...
0
votes
1answer
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, ...
-1
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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}|\}.$...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
2answers
30 views

Solving a recurrence having different sub-problem size using Master Theorem

Suppose I need to solve below recurrence using Master Theorem, $$T(n) = T(n/b_{1}) + T(n/b_{2})+ f(n)$$ Can I simplify the recurrence as below: $$T(b_{2}n/b_{2}b_{1}) + T(b_{1}n/b_{1}b_{2}) = b_{2}...
0
votes
0answers
23 views

Maximum length with special constraint NP Completeness Proof

I have this question to answer: For each node i in an undirected network $G = (N,E)$, let $N(i) = \{j \in N : \{i, j\} \in E\}$ denote the set of neighbors of node $i$ and let $c_e\geq0$ denote the ...
0
votes
1answer
21 views

Question about Complex Analysis and Residue.

I am studying Complex Analysis and I need to compute the residue of $f(z) = exp (1 + \frac{1}{z})$ on $z_0=0$ I Tried for Taylor Series,that is, $exp (1 + \frac{1}{z}) = \displaystyle \sum_{n=0}^{\...
1
vote
1answer
53 views

Algorithm to compute maximum independent set of graph with maximum block size k with comlexity $O(f(k)\cdot p(|V(G)|)$

Definitions Definition block: Let $G$ be a undirected Graph. A maximal 2-connected subgraph (subgraph without biconnected component) of $G$ is called a block. Definition maximum independent set: An ...
0
votes
2answers
36 views

Arithmetic Precision

I am reading a paper which states that four-byte arithmetic has accuracy $\delta \sim 10^{-7}$. Now as I understand it there are 8 bits in a byte so that makes 32 and one bit is used for the sign, 8 ...
0
votes
0answers
23 views

Computational complexity of nash equilibrium in continuous games

What is the complexity of computing a Nash equilibrium (or as a decision version, does a pure strategy Nash equilibrium exist?) for continuous games with the following structure? Each player solves a ...
0
votes
1answer
36 views

Series answer for larger constraints

So i have been solving a PnC question and now am stumbled upon a problem. Statement: Suppose we have an array of (n+m) size. Each element of array can be filled with any number from 0 to K. Now a ...
5
votes
0answers
32 views

NP-Complete proof of deciding if a graph has another Hamiltonian Circuit

I need to prove as an exercise that the following problem is NP-Complete: Given a graph and an already existing Hamiltonian Circuit in that graph, decide if the graph has another Hamiltonian Circuit ...
-1
votes
1answer
25 views

Clique of constant size

It is well known that Clique is a NP-Complete problem, But given some constant value K, finding whether a graph G has a clique of size K, is always a log-space (L) class problem?
-2
votes
1answer
22 views

How to calculate flops of matrix operations? [closed]

I am looking for a way or method to calculate flops of matrix operations, like sum or subtraction, multiplication, inverse, Singular Value Decomposition (SVD) operations and others, but I don't find ...
1
vote
1answer
23 views

Algorithm Complexity - For loop inside while loop; decreasing by factor 2

Question: What is the "correct" way to interpret the algorithm described below? I wanted to check if my understanding of the below algorithm is correct, as I haven't "encountered" this scenario where ...
0
votes
0answers
12 views

On the definition of internal and external information protocol

I feel like many places don't explicitly mention the definition of the internal and external information of a protocol (including the original paper in academia introducing it...), and would like to ...
1
vote
0answers
47 views

Evaluating the Sum $\sum_{r=1}^L \sum_{i=1}^L \left \lfloor \frac {L}{\left(\frac {r^2+i^2}{gcd(r,i)}\right)}\right \rfloor \cdot 2r$

Consider the following sum, bounded by limit $L$: $$\sum_{r=1}^L \sum_{i=1}^L \left \lfloor \frac {L}{\left ( \frac {r^2+i^2}{gcd(r,i)} \right )}\right \rfloor \cdot 2r$$ For better readability, ...
2
votes
1answer
47 views

Almost quadratic computational complexity

Suppose I can bound the running time of my algorithm as $O(a_N N^2)$ for any positive increasing sequence $\{a_N\}$ that diverges to infinity. Does this imply that my algorithm's running time is ...
0
votes
0answers
27 views

How to show that a language is in DTIME(n)?

how to show that this language is in DTIME(n)? \begin{equation} L=\left\{w w w : w \in \{a, b\}^{+}\right\} \text { is in } D T I M E(n) \end{equation}
0
votes
0answers
16 views

If $\varphi$ & $\psi$ are primitive recursive functions, show that $\tau$ is primitive recurisve.

I have the following question: If $\varphi :\mathbb{N}_0^{k+1} \to \mathbb{N}_0$ & $\psi :\mathbb{N}_0^{l} \to \mathbb{N}_0$ are primitive recursive functions, show that, by definition, $\mathbb{...
0
votes
0answers
18 views

What is the time complexity of a composition of polynomial reductions?

For example, if I have a polynomical reduction from A to B in $\mathcal{O}(n)$ time and a reduction from B to C in $\mathcal{O}(n^2)$ time, is the reduction from A to C in $\mathcal{O}(n+n^2)$ time?
0
votes
0answers
28 views

Find algorithm for maximum k blocks in Graph G in running time O(f(k) p(|V (G)|))

i am trying to solve this assignment for my college : If we have G as a connected graph and let k ∈ N be such that for all blocks B ⊆ G, | V (B) | ≤ k. how can we find ,without justification, an ...
1
vote
1answer
31 views

How can I show that $O( \sqrt{n} \cdot \log_2(n) \cdot \log_2(\log_2(n))) < O(n)$?

The question is pretty straightforward: How can I show that $$O( \sqrt{n} \cdot \log_2(n) \cdot \log_2(\log_2(n))) < O(n)$$ The question can be reduced by observing that $O(n) = O(\sqrt{n}) \...
1
vote
0answers
25 views

Complexity of a specific class of definite integrals

INTRODUCTION: From the answer to this question I learned that deciding whether a definite integral is $0$ or not can be NP-complete, as the following integral representation of the Number Partition ...
1
vote
1answer
21 views

Why the dynamic solution to vertex cover does not prove anything?

The dynamic programming solution implemented here runs in polynomial time, as discussed here on slide 18. My question is, why does this algorithm not hold value? Why cannot it be reduced to all other ...
1
vote
0answers
24 views

upper bound on, or fast algorithm to find, an order $2^n$ element in the multiplicative group modulo prime $q(2^n)+1$

I have a program which (in its current implementation) requires, for a given $N=2^n$, some $\omega$ in some field such that $\omega^N=1$ and $\omega^i\ne1$ for each $0<i<N$. Complex roots of ...
3
votes
2answers
25 views

exponential time complexity for $M(n,n)$ with $ M(i,j) = M(i-1,j) + M(i-1,j-1) + M(i,j-1) $.

For $n \in \mathbb{N}$ we define $Q(n) = M(n,n)$ with: $$ M(i,j) = M(i-1,j) + M(i-1,j-1) + M(i,j-1) $$ and $$ M(i,0) := M(0,i) := i \mbox{ } \mbox{ } \forall i \geq 0 $$ Show that $Q(n)$ (regarding ...
5
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
2
votes
2answers
54 views

Biased binary search complexity

We know Binary search on a set of n element array performs O(log(n)). We have this recursive equation through which the search space is reduced by half in each iteration, after a single comparison. <...
1
vote
0answers
29 views

Find first eigenvector of Hadamard division of $AA^T$ and $BB^T$ using power method

For an $m \times n$ matrix $A$, it is possible using the power method to find the eigenvector corresponding to the largest eigenvalue of $AA^T$ by factoring it into a matrix vector product $(AA^T)v = ...
0
votes
0answers
11 views

Strassen for Multiplying Three Matrices

Strassen algorithm works for multiplying only two matrices with arbitrary sizes (by using divide and conquer approach). I am wondering if there is an algorithm similar to Strassen but for multiplying ...
0
votes
0answers
14 views

Complexity limitations for randomness

I’m unsure if this is a stupid question, but: In general, is guessing a correct value faster when done randomly, or done incrementally from some basic seed/sequence? For example if I have [1,....,...
0
votes
0answers
6 views

How to show time complexity comparation of Fleury's and Hierholzer's algorithm?

I know that time complexity of Fleury's algorithm equals to $O(e^2)$ and Hierholzer's equals to $O(e)$. I need to show that Fleury's algorithm is less efficient on some example or by giving a proof of ...
0
votes
0answers
12 views

number of multiplications and additions

I would like to count the number of multiplications and addition in Cholesky Decomposition. Assume that I have Hermitian positive definite matrix. First, I will calculate all the entries in the lower ...
1
vote
0answers
32 views

Time complexity of finding neighbors of specific nodes within a threshold in a weighted graph

Let $G$ be a weighted graph and the weights are in the range $[0,1]$. Consider the list $A=[a,b,c,d]$ as a list of nodes we want to find the neighbors of each within a specific threshold $T$. What is ...