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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
39 views

Reference request:Computational complexity theory for GPU

I think that the computational complexity of the addition of Nth-order square matrices is $O(n^2)$ when using a CPU, but it is $O(1)$ when using a sufficiently large GPU. Is there a theory of GPU ...
user avatar
  • 53
1 vote
1 answer
28 views

How to programmatically calculate real eigenvalues and (optionally) complex eigenvectors for big matrix

I am trying to solve 1D timeindependent schrodinger equation $$ -\frac{\hbar^{2}}{2 m} \frac{\partial^{2} \psi}{\partial x^{2}}+V(x) \psi=E \psi $$ for periodic potential to simulate crystal lattice ...
user avatar
0 votes
0 answers
24 views
+50

Can we define limiting behavior function of higher order in terms of norms?

Let $f(x):=x$ and $g(x):=x^{2}$, then we say that $f=\mathcal{O}(g)$ if there exists $\alpha,x_{0}>0$ such that: $$ |f(x)|\leqslant\alpha|g(x)| $$ for all $x>x_{0}$ My question is if now $f,g : \...
user avatar
  • 293
0 votes
1 answer
27 views

finding the asymptotic growth bound for the following floor/ceiling recurrence

Suppose we have $$ T(n)=0 \quad,\quad n\leq3 $$ $$ T(n)= T(\lceil n/3\rceil)+T(\lfloor n/4\rfloor)+7n\quad,\quad n\geq4 $$ how does one show that the upper and lower bounds are matching? (i.e. find $\...
user avatar
  • 605
0 votes
1 answer
116 views

References for me to understand current approaches to settle $P$ vs $NP$ [closed]

I am an undergrad student that likes to study approaches to settle $P$ vs $NP$. I know that there is GCT method, and another way is to attack it by logic equivalent. I am a double major student in CS ...
user avatar
-3 votes
0 answers
11 views

What is the time complexity of initialization a static vector and determine functions?

I'd like to determine time complexity of a pseudo algorithm : Where specifying the variables A and B, is giving a value to A and B. Deterring the function E is choosing or writing the function E. ...
user avatar
  • 103
4 votes
1 answer
95 views

Good Algorithm to Compute all Subgroups of a Finite Group.

Let's suppose we have a group $G$ of finite order $n$. We want to algorithmically compute all subgroups, and there are some ways to do that. First one: Compute all subsets. Verify for each of them if ...
user avatar
0 votes
0 answers
15 views

What is the computational complexity of an equation composed of $2m^2$ divisions and $2m^2$ addition of $2n$ additions?

I want to calculate the computational complexity in term of the big (O). My equation is: Where the $S^+$ and $S^-$ are calculated as follows: Where $\triangle_TOPSIS$ It composed of $2m^2$ divisions ...
user avatar
  • 103
0 votes
1 answer
48 views

Asymptotic upper and lower bound for $T(n)=T(n-2)+\log n$

I'm trying to find the asymptotic upper and lower bound for $$T(n)=\begin{cases}0& n<2\\ T(n-2)+\log(n) &n\geq2\end{cases}$$ it follows that $T(n-2)=T(n-4)+\log(n-2)$, and therefore for $n\...
user avatar
  • 605
1 vote
0 answers
45 views

Determinant of triangular matrix with extra diagonal

If we have a triangular matrix we can calculate the determinant in $O(n)$. If we have a triangular matrix with one extra diagonal above the main diagonal, so for example: \begin{Vmatrix} a_1 & a_2 ...
user avatar
0 votes
2 answers
67 views

How can I calculate the computational complexity of an equation composed of $2n$ multiplications and $2nm^2$ additions?

I want to calculate the computational complexity in term of the big ($\cal O$). My equation is: It composed of 2n multiplications and $2nm^2$ additions. The complexity of this equation is it ${\cal O}...
user avatar
  • 103
0 votes
0 answers
4 views

Clarify answer for asymtotic of median smoothing

Calculating algorithmic complexity for median smoothing in Time Series I came up with the question same as this. Quote it here: A time series with T observations is given. Median smoothing with width ...
user avatar
  • 111
1 vote
2 answers
44 views

The rationale behind algorithm for the Modular Exponentiation from the book "Introduction to Algorithms"

I saw this pseudocode from the book Introduction to algorithm (Chapter 31 page 957) on how to implement Modular Exponentiation. ...
user avatar
  • 315
0 votes
0 answers
17 views

(possibly probabilistic) Complexity of recovering a function knowing image

So i ve nearly no knowledge on the subject but i decided to begin a reflexion on AI. And first this is what i discovered, and afer the related problem: Let say you have a set of word of {0;1} of same ...
user avatar
0 votes
0 answers
9 views

What is the time complexity to finding the least weight for Hamiltonian cycle in complete graph without finding best tour?

As we know finding the best tour in complete graph with n nodes, or the Traveling Salesperson Problem solved by the dynamic programming algorithm in $n^2.2^n$ time ...
user avatar
0 votes
1 answer
33 views

Reducing to an NP-complete problem

If $R$ is an arbitrary decision problem that is reducible to $S$, which is an NP-complete problem, what can be said about $R$? I think we should be able to say that $R$ is in NP since an instance of $...
user avatar
1 vote
1 answer
22 views

Time complexity of a surjection from natural number to non Hamilton graphs

I can build a $O(N)$ surjection from natural numbers to the set of Hamilton graphs with sizes less than $N$. For example, I can first map a natural number $x$ to a pair of numbers $(n, b)$, then $n$ ...
user avatar
0 votes
1 answer
23 views

Time complexity of getting $r$-largest eigenvalues and vectors of a symmetric matrix.

$A$ is a $n \times n$ symmetric matrix. I would like to know the time complexity of calculating $r$-largest eigenvalues and vectors. When we need all eigenvalues and eigenvectors, it means $r=n$, I ...
user avatar
-1 votes
1 answer
35 views

Size of coefficients in the proof of IP=PSPACE

I'm referring to the proof by Shamir. The polynomials transmitted in the protocol are of degree $\leq n$. Why does it mean that the polynomials could be transmitted in a polynomial size message? Is ...
user avatar
7 votes
1 answer
293 views
+400

How can one mathematically compute the security level of a human computable password schema?

Introduction As technology advances, cryptographers are developing improved techniques for encoding information. While these techniques are becoming incredibly efficient for computers to perform, I am ...
user avatar
1 vote
0 answers
14 views

BFGS computational complexity derivation

The update for the Hessian using BFGS is given by: $$H_{k+1}=(I-\rho_ks_ky_k^T)H_k(I-\rho_k y_ks_k^T)+\rho_ks_k s_k^T$$ where $\rho_k=\dfrac{1}{y_k^Ts_k}$. Nocedal and Wright, Numerical Optimization ...
user avatar
  • 576
0 votes
0 answers
17 views

How do you calculate the best/worst case complexity of an algorithm?

I have been given the example: ALGORITHM 1: Require: $n \ge 0 $ $x \leftarrow 1$ $\;\;\;\;\;\;$for $i = 1$ to $n$ do: $\;\;\;\;\;\;\;\;$$x \leftarrow x \cdot i$ $\;\;\;\;\;\;\;\;$ $i \leftarrow i + ...
user avatar
0 votes
0 answers
23 views

Each algorithm $f$ that checks each number is different than the others must make $\Theta(n\log n)$ comparisons

There are $n$ numbers and $<,=$ operators. Prove: Each algorithm $f$ that checks each number is different than the others must make $\Theta(n\log n)$ comparisons. Merge sort has $\Theta(n\log n)$ ...
user avatar
  • 1,561
1 vote
1 answer
39 views

Best way to compute $A^{-1}$ when the Cholesky decomposition $A=LL^T$ is known

Suppose $\mathbf{A}$ is symmetric positive definite, and that I have available the Cholesky decomposition of $\mathbf{A}=\mathbf{L}_A\mathbf{L}_A^T$. I want to know $\mathbf{A}^{-1}$. Which of the two ...
user avatar
0 votes
1 answer
69 views

On the general relationship between automata, expressions, and grammars

When I took Theory of Computation, the main points of interest were three kinds of automata: finite, pushdown, and Turing, one type of expression: regular expressions which are equivalent to finite ...
user avatar
1 vote
0 answers
33 views

Given a connected graph $G = (V, E)$, give a polynomial time algorithm that finds the set $U \subseteq V$ with the smallest boundary

So I asked something related to this a bit, but I don't think this is a duplicate in that I am providing a different version of the problem that is more generic and more easily accessible without ...
user avatar
0 votes
1 answer
60 views

Shattering of a set of binary classifiers

Let $S$ be a set, and let $\mathcal{F}_{S}=\{f:S\to\{-1,+1\}\}$ be a set of different label assignments. Show that $\mathcal{F}_{S}$ shatters at least $|\mathcal{F}_{S}|$ subsets of $S$. Here is what ...
user avatar
  • 445
0 votes
1 answer
28 views

Proof that Christofides Algorithm is a 3/2-approximation for the TSP

I have quoted a section of the proof for the above statement, from Williamson and Shmoys. Can someone explain the section in italics? "We want to show that the edges in the Eulerian Graph ...
user avatar
1 vote
3 answers
60 views

Prove whether $2^n = O(n^4 + n^2)$ is true

I have been given a set of questions on BigO for my university course, however I'm really struggling to wrap my head around it, and was wondering if anyone would be able to explain this example please?...
user avatar
2 votes
2 answers
64 views

What's the fastest way to solve a system of equations a million times such that the coefficient matrix is same but the constant matrix is different?

I need an efficient way to solve $Ax=C$ a million times such that coefficient matrix $A$ is always the same but the constant matrix $C$ is always different for each of the million problems. To solve ...
user avatar
0 votes
1 answer
207 views

Prove that there's no decidable language that separates two other languages.

I was reviewing for an exam and I found this question: Let A and B be two disjoint languages (that is, A ∩ B = ∅). Say that a language C separates A and B iff A ⊆ C and B ⊆ (not C) . Define two ...
user avatar
0 votes
0 answers
40 views

Given the value of a determinant what is the quickest way to calculate the value of a determinant which has only one column different?

I have a determinant $ \begin{vmatrix} a_{11}\ a_{12}\ a_{13} .... a_{1n}\\ a_{21}\ a_{22}\ a_{23} .... a_{2n}\\ .................\\ .................\\ a_{n1}\ a_{n2}\ a_{n3} .... a_{nn}\\ \end{...
user avatar
-1 votes
0 answers
38 views

How relevant would it be to prove that P vs NP is equivalent to P vs NP using only machines with one letter input alphabet?

I was reading the official description of P vs NP at https://www.claymath.org/sites/default/files/pvsnp.pdf out of curiosity and the authot says "Does $\textbf{P = NP}$? It is easy to see that ...
user avatar
0 votes
0 answers
26 views

Christofides Algorithm for the TSP: A "polynomial time approximation algorithm"?

I'm currently studying the travelling salesman problem and Christofides algorithm. I think I understand that TSP is an NP-hard problem, and so the complexity of calculating a solution grows ...
user avatar
0 votes
0 answers
23 views

Computational complexity sparse outer product

Suppose that I have a matrix $A$ of dimension $m \times m$, which can be computed as: $$A= X D X^\top$$ where $X$ is a matrix of dimension $m \times n$, with $m > n$, and $D= \operatorname{diag}(d)$...
user avatar
  • 354
2 votes
1 answer
31 views

Recursive algorithm complexity: Pedantic / Comprehensive proof

I'm trying to do a formal comprehensive proof of a certain recursive algorithm (Divide-and-conquer). My problem is that all resources I know always do some simplifications, and I don't manage to find ...
user avatar
1 vote
0 answers
43 views

Could integer factorization be approximable in polynomial time?(contained in APX) [closed]

This would mean that there is an algorithm that can take a semi prime, and return a number close to a factor of the semi prime, by some definition of the world close(this could also involve P-adic ...
user avatar
0 votes
0 answers
14 views

Definition of a time-complexity of a function $f:A\to B$

Let $f:A\to B$ be a function where $A$ and $B$ are at most countable sets. The bijections $\mathbb N\to A$ or $\mathbb N\to B$ are not unique, and I only know the time-complexity definitions for ...
user avatar
  • 1,277
1 vote
1 answer
68 views

If NL = P, prove that P!=PSPACE

If NL = P, how do we prove that P != PSPACE? Do we have to use Savitch's theorem?
user avatar
  • 11
1 vote
0 answers
42 views

Count graphs on $n$ vertices with at least one $\lfloor n/2 \rfloor$ sized clique

I am lookin for any reasonable formula for the number of graphs on $n$ vertices which have at least one $\lfloor \frac{n}{2} \rfloor$-clique. The naive attempt is to try to count all possible cliques ...
user avatar
  • 312
0 votes
2 answers
64 views

How to prove that 2SAT $\in$ P

I want to understand the proof in the following link for 2SAT $\in$ P... What for the need of the last corollary? Wouldn't be enought to just prove the case for the graph with the help of the path ...
user avatar
1 vote
1 answer
19 views

Binary Mathematical Operations Performed on Different Asymptotic Notations

I'm taking a course on the analysis of algorithms, and I'm trying to understand how different asymptotic notations interact with each other. For example, we learned that $$O(f(n)) + O(g(n)) = O(f(n) + ...
user avatar
  • 75
2 votes
1 answer
28 views

Maximum flow with minimal number of vertices used

In many of the research problems I encountered recently, the following version of the minimum cost maximum flow problem came up. We are given a directed graph $D$, a source vertex $s$ and a terminal ...
user avatar
  • 43
2 votes
3 answers
374 views

Why is it so difficult to prove $\mathbf{NP} ≠ \mathbf{P}$?

I'm just curious because I saw on Wikipedia a single polynomial time solution to any NP-hard problem would imply there are polynomial time solutions for every single NP problem. Also I assume there ...
user avatar
  • 283
0 votes
1 answer
48 views

Are complexity classes sets?

The definition of a complexity class reads in various different sources roughly as "a collection/set/... of decision problems". My question is: Is every complexity class a set (in the sense ...
user avatar
0 votes
2 answers
29 views

Proving NP Completeness of "the project manager's problem"

Suppose we have a list of basic/'atomic' tasks $\{p_1, ..., p_n\}$ and each task has an associated cost $c_i$ for all $i \leq n$. Morover, we have a list of projects $P_1,..., P_m$ which are ...
user avatar
2 votes
2 answers
102 views

Which grows faster $n!$ or $n^{\sqrt{n}}$?

From graph it can be easily seen that $n!$ grows faster that $n^{\sqrt{n}}$. Also wolfram alpha says that $\lim _{n\to \infty }\left(\frac{n^{\sqrt{n}}}{n!}\right)=0$. I'd appreciate if anyone could ...
user avatar
0 votes
0 answers
22 views

Evaluate Big O loop worst case and condition statements

Understanding big O, worst case in a loop. Im supposed to count assignation and comparisons, I dont get why? The other doubt I have is if the worst case is seeing/evaluated to infinity or for all the ...
user avatar
0 votes
0 answers
7 views

Given a poly(log(G), log(x)) algorithm and N>G, is it also poly(log(N), log(x))?

I have constructed an algorithm that runs in poly(log(G), log(x)). I am now asked to construct one that runs in poly(log(N), log(x)), where N>G. What would make the first algorithm not also run in ...
user avatar
  • 723
1 vote
0 answers
62 views

Make a sequence decrease to zero as fast as possible

Fix $d>0$, and let $n$ be a positive integer going to infinity, and for $h>0$, define $E=E(n,h)$ by $$ E(n,h) := h\sqrt{\log \frac{1}{h}} + \frac{1}{h}\sqrt{\frac{d\log n}{n}}. $$ A strategy $h=...
user avatar
  • 8,309

1
2 3 4 5
63