Questions tagged [computational-complexity]
Use for questions about the efficiency of a specific algorithm (the amount of resources, such as running time or memory, that it requires) or for questions about the efficiency of any algorithm solving a given problem.
3,287
questions
0
votes
0
answers
12
views
Complexity of Least Squares in Trust Region Reflective algorithm
Given a function $y=f(x,\theta)$, $N$ sampling points $(x_i,y_i)$ for $f$, I want to find the parameter $\theta$ (scalar in 1D) that most fit the $N$ data points , where $\theta$ is bounded in $b_L,...
- 101
4
votes
1
answer
139
views
Calculate $ \sum_{k=1}^{n} k\cdot \mu(k) $
Problem:
Given $n$, Calculate $ \sum_{k=1}^{n} k\cdot \mu(k) $
This is the oeis series.
My Thoughts:
I need a sublinear algo, possibly something of the order of $n^{3/4}$ or $n^{2/3}$ time. Any ...
- 451
3
votes
2
answers
193
views
Calculate $ \sum_{k=1}^{n} k\cdot\varphi(k) $
Problem:
Given $n$, Calculate $ \sum_{k=1}^{n} k\cdot \varphi(k) $
This is the oeis series.
My Thoughts:
Oeis gives a couple of approximate estimates/asymptotics but no real formula, exact closed form ...
- 451
1
vote
1
answer
59
views
The concepts of P, NP and NP_complete problems for the dummies
While there are already lot of questions on this topics here on Mathematics (1,2, 3) and several (too many perhaps) Wikipedia pages on the subject (a, b, c), they all involve concepts that I am not ...
- 239
-1
votes
1
answer
28
views
runtime complexity [closed]
i want to Order these runtime complexitys ascending.
I tried to transform this and made a first try in ordering them which you can find behind the -->
$log4711$ --> 1.
$log^4(n)$ --> 2.
$log(...
-1
votes
0
answers
33
views
Reduction : 3-Dimensional Matching $\leq$ $_{p}$ subset sum Explanation
excuse me, could someone explain to me the reduction of the problem 3-dimensional matching to subset sum? I was reading Jon Kleinberg's design algorithms book and when I came across this reduction I ...
- 51
1
vote
2
answers
46
views
Partition a positive integer sequence into subsequencies of equal weight
For a finite sequence of $N$ positive integers $a_1, a_2,.., a_N$ let us define its weight as
$w (\{a_i\}) = \log(N) \cdot \sum_{1}^{N}{a_i}$.
I want to partition such sequence into $K$ non-empty ...
- 130
1
vote
1
answer
27
views
Finding solutions to Boolean satisfaction problems
How hard is it to find a solution to an instance of SAT if we know that the instance is satisfiable?
Clearly, finding a solution to a SAT instance is at least as hard as deciding whether the instance ...
- 725
-2
votes
0
answers
9
views
The amortized complexity of visiting $m$ keys in order in B-tree with $N$ items
I read a paper that said the amortized complexity of visiting $m$ keys in ascending order in a $b$ tree with $N$ keys is $O(1 + \log(N/m))$. I am wondering why it is not $O(1 + (\log N)/m)$ because ...
7
votes
4
answers
436
views
In general, in a string of multiplication is it better to multiply the big numbers or the small numbers first?
Let's say we had to evaluate the following string of multiplications $5 \times 6 \times 7 \times 8$ , we could, for instance, order it by doing the biggest multiplications first:
$$ 5 \times \left( 6 \...
- 9,908
0
votes
1
answer
45
views
Is non-convex optimisation really in NP class?
I've seen in many optimisation papers the statement that general non-convex optimisation problem is NP-hard. If we assume that non-convex optimisation is in NP class, it can be shown, as I remember, ...
0
votes
0
answers
30
views
Feasibility of computing nth digit of a product of 2 integers?
I am trying to see if there is an efficient poly-time method of computing the $n^{th}$ digit of massively large integer products, where it would take even a fast computer an absurdly long time to ...
2
votes
0
answers
33
views
Variant of Assignment Problem with multiple group constraints
I have a bipartite graph $G = (G_1 \cup G_2, E)$ where we suppose $|G_1| \le |G_2|$.
Each vertex $V \in G_1$ represents a worker. A worker $V$ has two associated values:
a workgroup index $g(V) \in \...
- 21
0
votes
1
answer
47
views
Treatment of P and NP as sets in ZFC/NBG?
I have recently being working a lot with axiomatic set theory, and one of the first things I picked up on is that all members of a set are themselves sets. For example, $2 \in \mathbb{N}$ and $2 = \{\...
- 347
0
votes
1
answer
18
views
Worst-case time complexity of il-else block that iterates two disjoint sets [closed]
I am estimating the worst-case time complexity of this piece of code:
if (condition) {
// loop over A
} else {
// loop over B
}
such that A and B are disjoint ...
- 5
0
votes
0
answers
15
views
Fast matrix-vector product with transposed Vandermonde matrix
Let $a$ and $b \in \mathbb{C}^N$ be two complex vectors. Let $V_L(a)$ be the Vandermonde matrix of $a$ with $L$ columns
$$
V_L(a) = \begin{pmatrix}
1 & a_1 & a_1^2 & \dots & a_1^{L -...
- 101
2
votes
1
answer
19
views
Is One Way TSP NP-complete?
I know that One Way TSP (TSP but the salesman does not have to return to his original city) is NP-Hard, but is it NP-Complete? I ask this because I recently found a solution to Open TSP but can't find ...
- 127
1
vote
1
answer
45
views
What is the complexity of global solution of a nonlinear system?
Consider an $n$-dimensional system $F_j(x_1, \ldots, x_n) = 0, j = 1, \ldots, n$. The functions $F_j$ can be considered as monotonic w.r.t. all $x_i$. What is the complexity of the problem of finding ...
- 248
0
votes
1
answer
30
views
Notion of circuit width seems to have little to do with memory.
As suggested in the title, I'm unhappy with the notion of circuit width I've been given in my computational complexity class. It was motivated as a model of amount of memory needed for the algorithm, ...
- 409
1
vote
0
answers
84
views
Is there a general algorithm to decide whether an integer value is attainable by a quadratic form?
I'm not sure if I phrased the question correctly, but let's say that due to a result called 15 theorem that "if a positive definite quadratic form with integer matrix represents all positive ...
1
vote
0
answers
12
views
Proving the language 2-SIMPLE-PATH is in NL
The Question
I define the language$$\mathsf{2-SIMPLE-PATH}=\left\{ \left\langle G,s,t\right\rangle \left|\begin{array}{c}
\mathsf{there\;are\;two\;different}\\
\mathsf{simple\;paths\;from}\;s\;\...
- 242
1
vote
0
answers
29
views
Given two problems, is it always possible to reduce one of them to another?
Suppose we are given two problems $A$ and $B$ (both are solvable). Is it always possible to transform one of it to another? That means whether holds $A \preceq B, B \preceq A, or A \equiv B$.
This ...
- 11
0
votes
0
answers
32
views
Is there a way to solve this counting problem in linear or polynomial time?
I ask this question in math.stackexchange in the hope that this problem is a variation of or similar to an existing counting problem that has been researched previously:
There are $n$ teachers ...
0
votes
0
answers
25
views
Is uniform fault-tolerant K-median problem on an undirected graph solvable in polynomial time?
We know that the K-median problem is proved to be NP-Hard. In fault-tolerant K-median problem on an undirected graph $G=(V, E)$:
We are given a set of facilities $F\subseteq V$ and a set of demands (...
- 21
6
votes
2
answers
404
views
What does "NP-hard to distinguish ... between ... and ..." mean?
I am reading paper Hardness Results for Weaver’s Discrepancy Problem. In the abstract, the paper reads
it is NP-hard to distinguish such a list of vectors for which there is a signed sum that equals ...
- 695
1
vote
0
answers
21
views
Max-Weight-Clique and Max-Weight-Stable-Se
Let G = (V, E) be a simple undirected graph and $c ∈ Z^V$ weights on the nodes of G.
A vertex set C ⊆ V is called Clique if {u, v} ∈ E holds for all u, v ∈ C, with u not equal to v.
A node set S ⊆ V ...
- 101
0
votes
1
answer
53
views
Graph theory beginning
We now consider different arithmetic operations for vectors and matrices and want to
express the number of individual calculation steps as a function of n in the O -notation. By
the number of ...
- 101
0
votes
0
answers
15
views
What are the best books to learn distributed computation algorithms and principles?
I am wondering What are the best books to learn distributed computation algorithms and principles? I will just mention I am doing my master in applied math So I want a book that has an extensive ...
- 13
2
votes
2
answers
45
views
How would you compare $O((\log n)^k)$ in relation to $O(n^c)$? [duplicate]
How would you compare $O((\log n)^k)$ in relation to $O(n^c)$, $n,c \in \mathbb{N}*$ ? I'm very stuck on how to go about this.
I specifically need to see how $O((\log n)^{2021})$ relates to $O(n^3)$ ...
- 21
0
votes
1
answer
52
views
What is the big-$O$ size of a function like $\frac{n^n}{2^n}$?
So, it is clear that factorial (i.e., $O(n!) = O(n^n)$) growth rate outpaces that of exponential (i.e., $O(c^n)$ for a constant $c$).
However, what happens when we divide the two?
That is to say, what ...
- 1,763
1
vote
0
answers
21
views
What does it mean for a language L to be recognisable in polynomial time?
Does it mean there exists a TM which decides L in polynomial time - that is, for any input w, the TM decides in time polynomial in the input whether w belongs to L or not - or is it rather just that, ...
0
votes
1
answer
67
views
Complexity of differentiation (numeric vs. automatic/algorithmic).
I am reading about automatic differentiation and am wondering what the direct comparison is between the complexity of automatic (algorithmic) differentiation and numerical (finite difference) ...
- 99
0
votes
0
answers
47
views
Why is Gram-Schmidt algorithm the most efficient for finding an orthonormal basis?
Can you help me prove more formally, that, the Gram-Schmidt algorithm is the fastest algorithm for finding an orthogonal basis for the subspace spanned by a given basis, with the spanning property of ...
- 163
-1
votes
1
answer
110
views
Count number of solution to Diophantine equation $k_1a^2+k_2ab+k_3b^2-k_4c^2=0$
I am looking to count number of solutions of diophantine equation $k_1a^2+k_2ab+k_3b^2-k_4c^2=0$.
such that $ 1 \le a, b, c \le N$ and $gcd(a, b) = 1$
and $k_1,k_2,k_3,k_4$ are positive constant ...
- 451
2
votes
1
answer
70
views
Unsatisfying proof for NP-Problems
One common strategy to prove that a problem or language $L$ is NP is to show that there exists a certificate $c$ which can be verified in polynomial time by a (deterministic) Turing machine.
Let $\...
- 172
1
vote
1
answer
32
views
Is $b^{m+1} = O(b^m)$
For $b$ and $m$ being variables, is it the case that $b^{m+1} = O(b^m)$ ?
Any help would be much appreciated.
1
vote
0
answers
18
views
Computational Complexity of a Vector Sum Problem
i am asking myself what the complexity of the following problem is:
Given a non-negative integer vector $d \in (\mathbb{Z}_{\geq 0})^n$ and integers $k, m > 0$, i want to maximize $b^T d$, where $b ...
- 11
4
votes
1
answer
193
views
Find efficient way to generate all solutions to Diophantine equation $a^2+5ab+3b^2-c^2=0$ under a given bound $N$
I am looking to solve Diophantine equation $a^2+5ab+3b^2-c^2=0$.
a, b, c are all positive.
Since the number of solutions are infinite. Lets say we are only interested in solutions till a limit N ie $1 ...
- 451
1
vote
0
answers
24
views
Language of all graphs that have diameter larger than $\frac{n}{2}$
Let $$A=\{\langle G\rangle \mid G=(V,E) \text{ is an undirected graph, } |V|=n \text{ and } \text{diam}(G)\geq n/2\}$$
Show that $A\in NL$ by showing a log space decider.
I've tried to create a ...
- 23
2
votes
2
answers
131
views
How many ways we can partition a multiset, where each part/segment in the partition has distinct elements? [closed]
We define the set S as $\{(s_1, f_1), (s_2, f_2), ..., (s_i, f_i)\}$, where each $f_i$ is the frequency that $s_i$ is repeated in the multiset T. How many ways can we partition the multiset T into ...
0
votes
1
answer
51
views
The complexity of a variant algorithm for the Travelling Salesman Problem (TSP)
What is the algorithm's complexity for a variant of the TSP problem where every node must be visited at least once, meaning that a node can be visited more than once? (The cycle starts from a specific ...
0
votes
0
answers
22
views
Is there a strongly connected graph where 2 vertices exist such that random walk from one to another requires more than polynomial time?
The question is fairly simple: find an example of strongly connected (directed) graph $G$ on n vertices, such that degree of every vertice is at least $\frac{n}{2}$ and there exists a pair of vertices ...
- 1
3
votes
1
answer
63
views
Would undecidability of $P = NP$ imply its truth/falsity?
Suppose someone proved that the $P = NP$ question is undecidable from $ZFC$. Would that imply it is true? Would that imply it is false? I know that there are certain mathematical statements which, if ...
- 16.8k
1
vote
1
answer
36
views
Show that a function is linear if and only if it is $\theta(n)$
We have the following definitions:
Given two functions $s(n), t(n)$ on $\mathbb{N}$,
$s(n) = O(t(n))$ if there are constants $c, d$ such that for all $n$, $s(n) \leq c \cdot{t(n)} + d$
$s(n) = \...
1
vote
1
answer
28
views
Time complexity of a function
Can we categorize $f(n)=10+(-1)^n$ as exponential or polynomial ?
And how can I compare this function with functions like $g(n)=2^n$ and $h(n)=n^2$ so as to understand if it is greater or not? I know ...
0
votes
0
answers
33
views
What is the complexity of comouting multinomial coefficients through recursion?
I want to understand the complexity of evaluating Multinomial Coefficient through the following formula, assuming that each recursive call has a cost $O(1)$, I would like to know the general naive ...
- 1,697
3
votes
1
answer
121
views
Time complexity of computing Fibonacci numbers using naive recursion
I'm trying to rigorously solve the Time Complexity $T(n)$ of the naive (no memoization) recursive algorithm that computes the Fibonacci numbers.
In other words I'm looking for $f(n):T(n)\in\Theta(f(n))...
- 238
0
votes
1
answer
34
views
Complexity of enumeration of a recursive formula ? Given the recurrence on time cost?
Let $a_n$ represent the number of directed acyclic graphs on $n$ vertices. Then the wikipedia, gives me the following recurrence:
$$a_n = \sum_{k=1}^{n}(-1)^{k-1}\binom{n}{k}2^{k(n-k)}a_{n-k}$$
I want ...
- 1,697
0
votes
1
answer
45
views
What is the computational complexity of proving or disproving a polynomial inequality in one variable?
Lots of basic polynomial inequalities in one variable end up on Math.SE, so I'm thinking that a computer program can fix this once and for all by providing a detailed proof of a polynomial inequality ...
- 3,863
0
votes
0
answers
9
views
Why trial dividing r into n takes $O(\log(r)\log(n))$ operations
I'm very new to time complexity and i'm trying to understand this small part of a text i was given.
I have list of primes, $r$, up to a number P. My text says that trial dividing these $r$'s into $n$ ...
- 1