Computational complexity, a part of theoretical computer science that deals with understanding how efficiently a problem can be solved.

learn more… | top users | synonyms (1)

2
votes
1answer
18 views

Compute the SVD of $AB$ from the SVDs of $A$ and $B$

Knowing the SVD of $\mathbb{C}^{m*n} \ni A = U_A\Sigma_AV_A$ and $\mathbb{C}^{n*s} \ni B = U_B\Sigma_BV_B$, is there any way to speed up the calculation of the SVD of $AB = U_{AB}\Sigma_{AB}V_{AB}$? ...
0
votes
0answers
8 views

Oblivious Universal Turing Machine in $O(T \log T)$ time

Define a TM $M$ to be oblivious if its head movement does not depend on the input but only on the input length. That is, M is oblivious if for every input $x \in \{0, 1\}^∗$ and $i \in N$, the ...
-3
votes
2answers
32 views

Use big o or big theta to state complexity of an Algorithm (worst case) [on hold]

Hello can someone guide me through the steps to solve the complexity of an algorithm using big o and big theta, worst case, for example here's the algorithm: ...
0
votes
0answers
21 views

Define primitive recursive function

(it's not homework, this question is supposed to be supplementary material for students to understand the lecture material better!) I have specific function that needs to be proved to be primitive ...
0
votes
0answers
30 views

What is the best time complexity for this case?

I only want to know if the following system has any integer solution or not. Actually, I do not need to know the solution(s), and only need to know the answer of question "Does the system have any ...
8
votes
1answer
1k views

Divisor summatory function for squares

The Divisor summatory function is a function that is a sum over the divisor function. $$D(x)=\sum_{n\le x} d(n) = 2 \sum_{k=1}^u \lfloor\frac{x}{k}\rfloor - u^2, \;\;\text{with}\; u = \lfloor \sqrt{x}...
1
vote
1answer
51 views

Difference between NP-hard and NP-complete

I am struggling to tell the difference between the definitions of NP-hard and NP-complete problems. I know that NP-complete problems are NP-hard, so this tells me that $$\text{$P_1$ polynomially ...
1
vote
0answers
22 views

Proving that problem of finding the winner in symmetrical game is in NP

Recently, I've stuck in quite an interesting problem. Here's its full description: Consider a connected, non-directed, weighted graph G. In some $v \in V(G)$ stays a chip. Two players are playing ...
0
votes
0answers
40 views

Fourier-Motzkin elimination number of constraints

I have this question: Consider Fourier-Motzkin elimination algorithm. Let n = 2^p+p+2, where p is non-negative integer. Consider a polyhedron in R^n defined by the m = 8(n 3) constraints. +-xi+-xj+-...
0
votes
0answers
20 views

Determining bounds for a sum with nested infinite series

I am computing the inner product of the characters of the trivial and the $k$-th irreducible two dimensional representations of the dihedral group $D_n$ of order $2 n$ when $n$ is even. The ...
1
vote
0answers
134 views

Is Quadratically Constrained Quadratic Program (QCQP) in NP?

The general version of QCQP is NP-hard, but is it also NP-complete? That means, is there a non-deterministic algorithm, which solves QCQP in polynomial time complexity? If the general version of QCQP ...
1
vote
1answer
34 views

Are there strings with known Kolmogorov complexity?

I just looked into Kolmogorov complexity today and it appears to me that for a binary string of length $1$ (ex. '$0$') the Kolmogorov complexity must be $0$. It follows that Kolmogorov complexity ...
1
vote
1answer
448 views

Solving recurrence relation: $ f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3$

$f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3$ I have attempted to solve it by letting $n = 2^k$ $f(2^k) = 3f(2^{k-1}) - 2f(2^{k-2})$ Then set $S(k) = f(2^k)$ $S(k) = 3*S(k-...
0
votes
1answer
446 views

How do I prove an algorithm has $n^3$ time complexity?

Take the CYK algorithm outlined here: How to prove CYK algorithm has $O(n^3)$ running time In the top answer, how did that person go from the three summations to $t=(n^3−n)/6$ ? What's the method ...
2
votes
1answer
52 views

Hamiltonian circuit in at least one component

I'm having trouble proving that the problem stated in the title is NP-complete, specifically by reduction from Hamiltonian circuit. Intuitively it's clear - Hamiltonian circuit in one graph is NP-...
0
votes
1answer
75 views

Is it meaningful to search for “elegant” representations of mathematical objects?

For centuries we struggled with the concept of spatial rotations. We used to represent them in many different ways: mostly, Euler Angles and matrices. Those all had drawbacks and failed in specific ...
1
vote
4answers
65 views

I know that the binary and hexadecimal are useful, but what are the point of other bases, for example base 12?

I know about the uses of binary and hexadecimal, but what are the uses of other bases, for example base 12? (or duodecimal)
4
votes
2answers
502 views

How do you determine the complexity class of a problem like solving an integral?

The P and NP classes relate to decision problems, but what about calculus problems, specifically computing an integral? How does one figure out if a certain class of integrals is in P or NP? Can ...
0
votes
0answers
16 views

Computational complexity of multiplication of a matrix with a sparse vector?

If we multiply a $m \times n$ matrix by another $n \times p$ matrix, it has computational complexity $O(mnp)$. Suppose if I have an $n \times 2n$ matrix and an $2n \times 1$ sparse vector with only $...
4
votes
2answers
68 views

For which classes of matrix can the matrix exponential be easily computed?

We have diagonal matrices $A = \mbox{diag} (\lambda_1, \ldots, \lambda_n)$ for which matrix exponential has simple form $e^A = \mbox{diag} (e^{\lambda_1}, \ldots, e^{\lambda_n})$, and it can be ...
0
votes
0answers
32 views

Modified version of SubsetSum

Let $L=\{(y_1,...,y_n,S,p)\ |\ \exists I\subset[n]\ s.t. \ |I|=p.\ \sum_{i\in I}y_i=S\}$. and $\forall\ 1\leq i\leq n\ :y_i \text{ is a positive integer}$, Assuming $\mathcal{P}\neq\mathcal{NP}$. ...
0
votes
0answers
8 views

Complexity class for subsumption for $\mathcal{AL}(\circ, ^{-})$

According to Baader et al's Description Logic Handbook, subsumption for $\mathcal{AL}(\circ)$ and $\mathcal{AL}(^{-})$ is in $\mathrm{P}$. However, I am not sure what complexity class subsumption for $...
-1
votes
1answer
51 views

$L\in P$ prove that $L^*\in P$

I have that question that looks kinda easy at first but it is quit hard. Let $L\in P$ prove that $L^*\in P$ (L is a language and P is the class of all problems which can be decided by a ...
0
votes
0answers
25 views

What is the proof that boolean circuit can be arranged as alternating OR and AND gates

In circuit complexity, a branch of compuatation comlexity theory, a theorem is that any boolean circuit can be written equivalently as a hierarchical structure, in which the first layer consists of OR(...
6
votes
1answer
2k 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
32 views

NP problem that has a verifier that uses $\leq 3 \log_2 n$ bits of memory, how does that influence the complexity of the problem itself?

Translated exercise: Algorithms, that solve NP problems. Let's assume a problem $R$ is in the set $\sf NP$. A verifier $M(x,y)$ for this problem works in time $O(n)$ and uses extra information $...
0
votes
0answers
8 views

Books on computational complexity which contain method for representation

It seems very important to know how to represent mathematical objects as binary strings in Computational Complexity. However, these methods of representation are often missing in most of the standard ...
2
votes
0answers
54 views

Undecidable problems involving elementary functions

I am reading the article "Some undecidable problems involving elementary functions of a real variable" by Daniel Richardson and have some problems with understanding Lemma Three : Let $h(w)=w\sin w, ...
0
votes
0answers
7 views

Determine time complexity for a given magnitude algorithm

$\mathbf{Question}$: Given magnitude $N$ and function $f(n)$, is the time complexity for the sum $s(f)$ of values $f(n)$ for $n=0\to N$ greater than $f(n)$ when $f(n)$ increases at a slower rate than ...
0
votes
0answers
12 views

Time Complexity of Kalman filter and RTS smoother

Predict Step: $k= \{1,2,..., n\} $ $\mathbf{\hat{x}}_{k|k-1}=\mathbf{F}_{k-1}\mathbf{\hat{x}}_{k-1|k-1}+\mathbf{g}_{k-1}$ $\mathbf{\hat{P}}_{k|k-1}=\mathbf{F}_{k-1}\mathbf{\hat{P}}_{k-1|k-1}\mathbf{F}...
0
votes
0answers
11 views

what is the time complexity of checking the conservation of flow in a network?

As you may know, considering a network with the set of nodes $V$, the conservation of flow law is the followings: $$\sum_{v \in V} f(u, v) = 0, \quad \text{for all $u \in V \setminus \{s,t\}$}$$ and ...
0
votes
0answers
32 views

How can I solve this Big $O$ exercise? [duplicate]

How can I prove that $n \log_2(n) ∈ O(log(n!))$ is true? We start by supposing that $f(n)< c g(n)$ is true, which means that $n \log_2(n) > c \log(n!)$ for all $n>n_0$ and $c>0$.
2
votes
2answers
21 views

Complexity notation (Omega) consequence

In my algorithms class, the professor told us that the following holds: $$ \text{If } f(n) = \Omega(\log_2 n) \implies 2^{f(n)} = \Omega(n)$$ But is this always true ? I couldn't come up with a ...
1
vote
0answers
27 views

Computational complexity of conjugate gradient method for a positive semidefinite Hermitian matrix

Let us assume that we want to solve the linear system: $$\mathbf{A}\mathbf{x} = \mathbf{b}$$ with the conjugate gradient method. $\mathbf{A}$ is a positive semi-definite Hermitian matrix. The ...
0
votes
1answer
441 views

checking boolean logical equivalence

Given two boolean formula (aka. logic circuit), I want to check if they are logically equivalent, namely that they compute the same truth table. Is this an NP-complete problem? What is the proof?
0
votes
0answers
29 views

What is computational complexity of a coding technique

In my previous Question Help in understanding a coding technique based on inverse mapping of a dynamical system I learnt how to apply chaotic map in coding theory in communications. Steps: (1) The ...
0
votes
0answers
19 views

Time complexity analysis of partitioning method

http://www.stat.cmu.edu/~cshalizi/462/lectures/05/05.pdf tutorial explains about how a generating partition can produce 0/1 symbols from a dynamical system. The technique is called Symbolic Dynamics. ...
0
votes
1answer
177 views

How to show a function is negligible?

Let $neg(x)$ be a negligible function (see here for the definition). Let p be a polynomial function such that $p(k)\geq 0$ for all $k>0$. What can we say about $f = neg(p(k))$? Is $f$ a ...
1
vote
1answer
449 views

Computational complexity of Gaussian elimination

If it took me approximately 4 minutes to solve an equatian $Ax=b$ for $x$ (where $A$ is a $3\times3$ matrix and $b$ is a $3\times1$ matrix) using Gaussian elimination, how much longer would it take me ...
7
votes
1answer
109 views

Can these definitions of the words “problem” and “solution” be formalized, and if so, has this been done? If so, where can I learn more about it?

I had a thought. Define that: Vague Definition 0. A problem consists of: a set $X$ a set $Y$ a function $f : X \rightarrow Y$ a way $\overline{X}$ of representing the elements of $X$ ...
0
votes
1answer
14 views

Asymptotic notation basics

Say that we have the function $$ f(n)=kn, \, k>0 $$ does that imply the following? $$f(n) \in O(n), \, f(n) \in \Theta(n) \text{ and } f(n) \in \Omega(n)$$ I'm fairly new to these notations and am ...
0
votes
0answers
7 views
1
vote
1answer
30 views

How to solve master theorem $T(n) = 3T\left(\frac{n}{2}\right) + \frac{n^2}{\log_2 n}$

Im trying to solve this using master theorem $T(n) = 3T\left(\frac{n}{2}\right) + \frac{n^2}{\log_2 n}$ but I dont know how. So far we know that $a=3$, $b=2$, $f(n) = \frac{n^2}{\log_2 n}$. Which ...
0
votes
1answer
61 views

What does $\forall X: A^X \subseteq B^X$ mean?

In Greg Kuperberg's complexity zoology inclusion diagram, there is a color coding based on whether or not $$ \forall X : A^X \subseteq B^X $$ is proven, disproven, or unknown. What does this ...
0
votes
0answers
137 views

Can all programs reducible to ones with only arithmetic operations on inputs be simulated with polynomial overhead by arithmetic machine?

In Can all programs be modeled as operations of elementary arithmetic operations on inputs? and computability theory, I asked: we treat all inputs and intermediate results and final outputs as ...
0
votes
1answer
15 views

Is there a Relationship Between Multi-Valued Logic and n-Satisfiability?

Is binary (Boolean) logic related at all to the two-satisfiability problem? And is ternary logic related in some way to the three-satisfiability problem? Would it follow then that if one were to ...
1
vote
1answer
46 views

Master theorem with $f(n) = n\log(\log n)$

I have a question related to algorithm time complexity and master theorem. How to solve this master theorem $T(n) = 2T(n/2) + n\cdot \log(\log(n))$? We have 3 cases: I don't know which one to ...
1
vote
0answers
39 views

Running time of Edmonds-Karp algorithm

I have to prove that the running time of the Edmond-Karp-Algorithm is $\Theta({m^2}n$) by providing a family of graphs, where the Edmond-Karp-Algorithm has a running time of $\Omega({m^2}n$). I have ...
2
votes
1answer
24 views

Busy Beaver unprovoable for large inputs?

From Wikipedia on the busy beaver, there is a true-but-unprovable sentence of the form "$Σ(10↑↑10) = n$", and there are infinitely many true-but-unprovable sentences of the form "$Σ(10↑↑10) < ...
0
votes
1answer
56 views

How quickly can this function be computed?

I can show that $\lambda (n)=i^{\tau(n^{2})-1}$, where $\lambda (n)$ is the Liouville function, $\tau(n)$ is the divisor function, and $i$ is the imaginary unit. My question is as stated, and what is ...