# Tagged Questions

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

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 ...
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 ...
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,...
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 ...
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 ...
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 ...
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 ...
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. ...
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? ...
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 ...
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?
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 ...
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 ...
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 ...
22 views

33 views

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....
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 ...
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 ...
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}$? ...
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: ...
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 ...
1k views

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 ...
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+-...
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 ...
135 views

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 ...
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 ...
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 ...
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-...
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 ...
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)