Questions tagged [time-complexity]
Time complexity of decision problems or relations among time-bounded complexity classes. (Use the [analysis-of-algorithms] tag for the time taken by particular algorithms.)
432 questions
2
votes
1
answer
926
views
In what sense is this algorithm better than Dijkstra?
A recent publication (Duan, Ran, et al. "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths." Proceedings of the 57th Annual ACM Symposium on Theory of Computing. 2025) ...
- 83
0
votes
1
answer
370
views
I have written a preprint about a novel algorithm to find MST, I think it can be a replacement for Kruskal's algorithm; Can any anyone review it?
I am a recent CS Grad, and I wrote a preprint about a algorithm for MST, with time complexity O(E+VlogV) and Ω(E) in the worst and base cases, respectively; given sorted edges. I feel like it is a ...
0
votes
1
answer
244
views
How can we solve Hitting Set instance in time $O(2^k)$ using Dynamic programming, where $k$ is the number of sets?
Suppose we have a hitting set instance $(U, F)$ where $U$ is the universal set and $F$ is the family of subsets of $U$. $F$ has $k$ many sets $=\{f_1, f_2,...,f_k\}$ and $U$ has $n$ many elements. ...
- 21
0
votes
1
answer
138
views
How do tree-width, clique-width and rank-width meta-theorems for (#2)SAT relate to the primal vs. incidence graph?
I’m trying to get a clear picture of the various “width-based” metatheorems for SAT/#2SAT, and in particular:
Which graph are they measuring?
The primal (constraint) graph (G) on variables, with an ...
- 131
6
votes
1
answer
285
views
Efficient matrix multiplication in small space
Just a clarification on parallel algorithms.
The answer in
Parallel algorithms for directed st-connectivity states "All Strassen-like algorithms for matrix multiplication (including the one by ...
- 13.7k
2
votes
1
answer
270
views
Lower bound for undirected graph connectivity
Suppose we have an undirected graph represented by an adjacency list. In particular, we have full random access, in one step of computation we can access the $j^{th}$ neighbor of vertex of $i$. ...
- 123
2
votes
0
answers
34
views
Inserting a shuffled sequence into a binary heap
Take a sequence of $n$ distinct elements and shuffle it, so that each permutation is equally likely. Now starting from an empty binary min heap, insert our items one by one. We insert by the usual ...
- 168
6
votes
1
answer
244
views
Time hierarchy for problems which are almost in P . (99%-P/O(1))
We say that two functions $f,g$ from $\{0;1\}^\ast$ to $\{0;1\}$ are 99% similar if, when $n$ is big enough, they agree on 99% of inputs of size $n$, i.e. $\exists n_0, \forall n>n_0 P_{x\in \{0;1\}...
- 459
4
votes
1
answer
406
views
Checking if a DAG uniquely connects sources to sinks
Consider the following decision problem: given a directed acyclic graph, is there a unique path from each source (vertex of in-degree zero) to each sink (vertex of out-degree zero)?
What is the time ...
1
vote
0
answers
54
views
Worst and average case time complexity of a k-dimensional prefix search in a kd-trie?
TL;DR
What is the time complexity of a $k$-dimensional prefix search in a "$k$d-trie" (not a "kd-tree") in the worst and average cases ?
Here, the $k$d-trie is a standard trie that ...
- 21
1
vote
0
answers
55
views
For a given semiprime hard to factor, what's the probability to find an Integer that will lead to a perfect square in the Adolf Kunerth’s algorithm?
The Kunerth’s algorithm is a non‑generic algorithm for finding modular square roots against a composite modulus without factoring it in polynomial time.
If I understand it correctly, it relies on a ...
- 121
2
votes
1
answer
168
views
Proving verification complexity is bounded by computation complexity in RAM
I am not a computer scientist, so I am not sure if this question even makes sense. Please forgive me if it does not. I am not sure if the terminology I am using is correct or not.
Let us consider a ...
- 121
0
votes
0
answers
78
views
Computational complexity of a complex exponential sum
Suppose that $\varphi_1, \dots, \varphi_n$ are $n$ real numbers. Given $c \in [0,n]$, we want to find the smallest $t > 0$ such that:
$$
\left\vert \sum_{k=1}^{n}e^{i \varphi_k t}\right\vert \leq c
...
- 2,854
2
votes
1
answer
132
views
On what functions on strings of length $n$ are we able to compute the Kolmogorov complexity and also exhibit an optimal program?
I'm interested in applications of optimal programs that convert one formal language into another (in particular Python to C++) so this seems highly related. I am thinking along the lines of "...
- 236
3
votes
0
answers
183
views
How to efficiently determine disconnects in a dynamic graph after performing N deletions and M additions
PS: New to this SE, but old time SE/SO user.
Background study - I've gone through this, computer science and computational science SE and also various papers (skimmed) related to fully dynamic ...
- 31