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)

0
votes
0answers
8 views

Approximating $L_n[1/3, 1.92]$ for GNFS

Approximating the RHS of $T(n) = L_n[1/3, 1.92]$ Perhaps related to this earlier question on the cost of running the GNFS, I am looking for an approximation for solving equations of this form, when $...
0
votes
0answers
50 views

Exam Recurrence and Complexity [on hold]

I have an exam coming up in a few days and my prof gave us a couple questions we should know as he will make new questions based on these topics the explanations must be in-depth because it will be a ...
0
votes
1answer
9 views

Why is the running time of the trial division $O(f \cdot (log N)^2)$?

I saw this being cited in a few paper,but none of them seems to explain why this is the case. Maybe because it is quite trivial, but I am not sure why exactly... Here $f$ is the size of the factor. I ...
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}$? ...
-3
votes
2answers
32 views

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

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 ...
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 ...
1
vote
1answer
52 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 ...
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
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
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)
0
votes
0answers
17 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 $...
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
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}$. ...
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
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
52 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(...
0
votes
1answer
77 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
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 ...
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
12 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
30 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 ...
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
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

Why %RSD of execution times, while sorting hundreds of arrays, is lower for larger arrays of random integers?

I am experimenting with the sorting of arrays and their execution times. While using bubblesort, insertsort and ...
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
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
41 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) < ...
2
votes
0answers
24 views

Algorithmic complexity of testing whether a permutation belongs to a subgroup generated by a set of permutations

Let $S=\{S_1,S_2,S_3,\ldots,S_m\}$ be a set of permutations on $n$ symbols (in other words $S$ is a subset of a symmetric group on $n$ symbols) and $P$ be a permutation on $n$ symbols. What is the ...
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 ...
1
vote
0answers
16 views

Is there any example of real-life decidable problem that is not in EXP?

In order to illustrate an introduction on computational complexity, I am trying to find examples of real-life problems for every one of the main complexity classes: $P$, $NP$, $EXP$, $R$ and ...
1
vote
1answer
22 views

Describe a polynomial-time algorithm to compute the function expressed by the boolean formula

Let $\varphi$ be a boolean formula of $n$ variables and $(t_1, t_2,\ldots,t_n) \in \{0, 1\}$ be an assignment. How to describe a polynomial-time algorithm to compute $\varphi(t_1,t_2,\dots, t_n)$?
0
votes
0answers
10 views

Computational complexity of a feasibility LP with $m$ inequalities, in $d$ dimension?

How would you quantify the computational complexity of feasibility LPs? Say for example an LP with $m$ inequalities : $$ \begin{cases} \mathbf{a_i}.\mathbf{x} \leq b_i, i \in [m] \\ \mathbf{x} \in \...
2
votes
0answers
24 views

One way functions and P = NP?

How can I show that no one way functions exist under assumption of P = NP?
4
votes
1answer
105 views

Cryptosystem safer than RSA

As you know, the RSA system is based on the fact that factoring a number $n$ cannot be done in polynomial time ($P(\ln(n))$, not $P(n)$). The factoring problem is known to be in $NP$, but we don't ...
0
votes
1answer
40 views

Proving that $\log x$ is Big Oh of $x^k$ for every positive k

Can I know a way to prove the above condition purely by the definition (and may be Taylor Series) and without using L'Hospital's rule? It is obvious for k greater than or equal to 1 but how can you ...
0
votes
0answers
6 views

Time complexity for recursion

For, this recursion, What's the time complexity? T(n) = 3T(n/2) + O(log n) I think I can't use the master's theorem because a = 3, b = 2 then log2(3) = 1.58 and f(n) = n^0*log(n), so c = 0 and it ...
0
votes
1answer
24 views

Time complexity for loop with pow and log n advancement.

So, I'm analyzing this loop. And I'm not sure of the time complexity. ...
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$ ...
1
vote
3answers
43 views

What is the value of $x$ when $a^\frac{1}{x}=1$?

I used to compute complexity of an algorithm which reaches to constant value after x level because of $a^\frac{1}{x}=1$. Now I need to find $x$ to reach answer. To describe more : my recursive ...
0
votes
1answer
32 views

Time complexity for inner loop

What's the time complexity for this code? ...
1
vote
0answers
19 views

How can we make Cook-Levin Reduction an implicit log space reduction

This is an exercise mentioned in lots of places. I have searched around for detailed answers, but none of them has explained clearly on a critical part of analysis. Setting: we have an oblivious ...
12
votes
1answer
281 views

How to formulate the P v.s. NP problem as a formal statement inside the language of set theory?

I've read a lot that some computer scientists believe that P v.s. NP could turn out to be independent of ZFC. The thing that puzzled me is how to formulate this inside the language of set theory? I ...
0
votes
0answers
31 views

If graph isomorphism yields a polynomial time algorihtm.

Greeting I'm studying computing theory and are trying to grasp the concept of complexity classes. If graph isomorphism (suspected NPI) turns out to have polynomial time solution. What possible ...
2
votes
1answer
33 views

Enumerating the primitive recursive functions without repetition

According to this paper (and this one), it is possible to enumerate the primitive recursive functions without duplication, even though equality of primitive recursive functions is not decidable. I am ...