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)

4
votes
1answer
54 views

What is the computational complexity of calculating $\pi(x)$ exactly?

The prime counting function $\pi(x)$ has been determined for $x=10^{26}$. The list of the $10^n$-th primes , however , ends at $n=18$. The $10^{18}$-th prime has $20$ digits. Apparantly, the ...
1
vote
0answers
13 views

CLRS substitution method “subtracting constant” technique

I'm reading CLRS, and in Chapter 4 it states that if you guess the asymptotic complexity of a recurrence correctly but cannot quite get the mathematical induction work out, a common method to employ ...
0
votes
0answers
20 views

Upper and lower bound for maclaurin series of exponential function [on hold]

I have an algorithm like this: The algorithm and I want to find upper bound for O() notation and lower bound for Ω() notation. When I try debug the algorithm, It is maclaurin series but without 1,...
0
votes
0answers
19 views

A graph is said to be in Hamiltonian cycle. Then the travelling salesman problem is? [on hold]

The graph ‘g’ with vertices {A, B, C, D, E } is said to be in Hamiltonian cycle. Then the travelling salesman problem is Heuristic NP-complete minimal spanning tree triangle inequality My ...
2
votes
1answer
71 views

Discrete logarithm modulo powers of a small prime

Is there an efficient way to compute $x$ in $2^x \equiv b \pmod {p^m}$, where $p$ is a small odd prime and $m$ could be a large integer? I know the solution is of the form $x=\phi(p^m) k + y$ for ...
1
vote
0answers
15 views

What are the methods for solving ODEs with accuracy higher than Runge Kutta 4?

Usually, justification of using RK4 is the following: "RK4 demonstrates a better approximations than Euler and Modified Euler methods of solving ODEs and offers a good balance between accuracy and ...
2
votes
1answer
63 views

Are derivatives actually bounded?

Suppose you a function $f$ which is differentiable, with the property that $$ f^{(n)} (0) = (n!)^2 $$ And in general $$ f^{(n)} (a) = O((n!)^2)$$ For any $a \in \mathbb{R}$. This function ...
0
votes
0answers
40 views

How does the induction proof work in this solution?

Refer to answer 1.1 of this file: http://www.dei.unipd.it/~geppo/AA/DOCS/NPC.pdf From my understanding and this thread, http://math.stackexchange.com/a/928412, we need 3 steps for that proof. ...
2
votes
2answers
45 views

Find least number of radial-subgraph of a graph

Background: Here is a group G of a people, one maybe another's friend. How to select least number of people to be a leader of a subgroup, so that everyone in the group G has a friend as a leader? ...
0
votes
1answer
18 views

Bin packing approximation algorithm

I know that bin packing cannot be solved in $\mathrm P$ unless $\mathrm P=\mathrm{NP}$, because we could solve partition problem. However, I do not see why this theorem is a collorary. There is ...
0
votes
1answer
14 views

How complexity of algorithms are compared

I have two algorithms one with complexity $O(100)$ and the other with complexity $O(270)$. Can anyone give me a clear explanation of what exactly this means and how they are compared?
0
votes
1answer
71 views

Find solutions of $a + b + c$ even, $3a + 2b - 3c$ odd, $a - 7b + 8c$ odd, in polynomial time

Suppose I have a linear equation in $3$ variables $a$, $b$ and $c$. \begin{align} \begin{cases} a + b + c &= 40 \\ 3a + 2b - 3c &= 49 \\ a - 7b + 8c &= 77 \end{cases} \end{align} The ...
0
votes
0answers
24 views

Linear regression of matrix elements to get the minimal polynomial to perform a matrix inversion?

So each matrix $\bf A$ fulfils an equation for it's minimal polynomial $P_m({\bf A})$: $$P_m({\bf A}) = 0 \Leftrightarrow \sum_{k=0}^{k_n}c_k{\bf A}^k = 0$$ We can by multiplying with $A^{-1}$ and ...
0
votes
1answer
47 views

Analysis of bisection search

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/unit-1/lecture-3-problem-solving/ In the following video i'm ...
1
vote
0answers
22 views

When is $\frac{2 n f(n)}{n !}$ in the order of some fixed power of $n$?

I would like to know when $\frac{2 n f(n)}{n !}$ is $O (n^b)$ where $b$ is a constant. Here, $n$ is a positive integer. My attempt: $$ \frac{2 n f(n)}{n !} = \frac{2 n f(n)}{\sqrt{2 \pi n} (\frac{n}{...
1
vote
0answers
131 views

Is 0-1 integer programming always NP-hard?

I have the following problem. Maximize $\sum\limits_{m=1}^M\sum\limits_{n=1}^N x_{mn}$ subject to: $\sum\limits_{\substack{m^\prime=1\\ m^\prime \neq m}}^M\sum\limits_{\substack{n^\prime=1\\ n^\...
1
vote
1answer
453 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-...
4
votes
2answers
75 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
14 views

Is there a simple way to describe all $O(n)$ algorithms given simple assumptions about the machine?

For example, can all $O(n)$ algorithms (where $n$ is strictly an integer) be described as: for k in 0..f(n): O(1)(k) where $f$ is a linear polynomial in $\Bbb{...
0
votes
1answer
13 views

Is $\{\langle M \rangle \mid \exists P \;\text{(p is polynom)}\; \forall w\; \text{M(w) halt with less than p(|w|) steps}\} \in RE$?

Is $L=\{\langle M \rangle \mid \exists P \;\text{(p is polynom)}\; \forall w\; \text{M(w) halt with less than p(|w|) steps}\} \in RE$? I can prove that $L \notin coRE$, but I don't know what to do ...
0
votes
1answer
26 views

Hardness for problems with non constant input parameters.

It's well known that problems like $3$-sat and $4$-sat and probably $k$-sat for $k\geq 5$ are NP-hard problems but what happens for example if i was to consider something like $\lceil \mathrm{log}(n) \...
1
vote
0answers
23 views

For What Families of Subgraphs, the Subgraph Isomorphism Problem Can be Solved in Polynomial Time?

Are there families of subgraphs that are arbitrarily large and are still easy to match in a larger graph ? By a "family" I mean a graph sequence $\mathcal{G}=\{G_1,G_2,\ldots,G_n,\ldots\}$ which is ...
2
votes
1answer
33 views

A correct expression for Hardness?

I'm interested in whether it's possible to express the hardness of a result in the following form. 1.For example: Suppose $A(n)$ is the class of graphs for which the minimum degree $\delta(G)\geq n/...
0
votes
0answers
13 views

Why does potential interactions and collisions increases as $^nC_2$ or $O(n^2)$?

Why, when we have $n$ robots navigating in 3-D open space to $n$ independent goals, the complexity increases with $n$? According to the anwer given by my teacher, it is because the number of ...
0
votes
1answer
32 views

Finding eigenvalues and complexity of calculating determinant vs reducing matrix

I was given the matrix $$A=\begin{pmatrix}1 & 0 & -4 & 4\\ 0 & 2 & 0 & 0\\ 0 & 1 & 1 & 0\\ 0 & 1 & 0 & 1 \end{pmatrix}$$ and told to try and "guess" it'...
0
votes
0answers
25 views

Pollard's $\rho$ algorithm and quadratic sieve

I am wondering why is quadratic sieve better than Pollard's $\rho$ for integer of $10^4-10^{10}$ digits? The running time of quadratic sieve is $e^{(1+o(1))\sqrt{\ln n\ln \ln n}}$, but the Pollard's $\...
1
vote
0answers
32 views

What is the computational complexity class of thermal photon statistics

I would like to know the computational complexity of the following formula for the variance of thermal photon statistics. $$P(n)=\sum_{d=1}^D\prod_{m=1}^M\frac{1}{(1+\langle n_m \rangle)(1+\langle ...
0
votes
1answer
33 views

reductions from $SAT$ to $DSAT$ and $DSAT$ to $SAT$

can someone help me to prove or disprove the 3 claims about reductionsbetween $SAT$ and $DSAT$, where: $SAT=\{<\phi> | \text{$\phi$ is bolean formula in $CNF$ and there is an interpretation ...
0
votes
1answer
453 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
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
10 views

Estimate the complexity for number times the function n/ lgn will be called recursively such that the result is a constant c = 2?

Cormen exercise $3.6$ which defines recursive function $f(i)$ such that $i$, $i \ge 0$ and the function is recursively called on itself $f(….f(i))$ such that it reaches a constant $c= 2$. Please help....
0
votes
1answer
11 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 ...
1
vote
1answer
458 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 ...
2
votes
1answer
21 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 ...
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
55 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
27 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
44 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
135 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
36 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 ...
0
votes
1answer
448 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
53 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
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
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
512 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
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 $...
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}$. ...