# Tagged Questions

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

14 views

### Complexity of matrix inverse

I'm trying to determine the exact complexity of finding an $n\times n$ matrix inverse of $A$. If it is known that the complexity of Gaussian elimination if $\frac{2}{3}n^3 + \frac{1}{2}n^2+O(n)$, then ...
14 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 ...
21 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,...
20 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 ...
57 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 ...
16 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. ...
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 ...
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? ...
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?
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 ...
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 ...
22 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....
8 views

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-...
33 views

54 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 ...
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(...
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 ...