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.)
396
questions
2
votes
0
answers
86
views
Is the following special case of multiway number partitioning NP-hard?
The following problem is a decision problem of multiway number partitioning (wikipedia) (Note that $k$ is also a part of an input in the following problem, while $k$ is a fixed number in wikipedia ...
- 21
1
vote
0
answers
40
views
How to deal with the time to minimize a function in a given interval?
I'm writing a paper in which I designed an algorithm running in $O(n^2m)\cdot T(f)$ to solve my problem, where $n,m$ is the size of input and $f:\mathbb{R}\rightarrow \mathbb{R}$ is a function, and $T(...
- 461
1
vote
1
answer
161
views
3-SAT runtime if an optimal order to eliminate possible solutions is known
As a mental exercise I have been playing around with the 3-SAT problem, but I am having difficulty proving or disproving the usefulness of a current idea that I am playing around with.
My current ...
0
votes
0
answers
111
views
Subset Sum Problem exact Algorithm (hypothetical)
Let assume there is way to apply a divide & conquer approach to the classical subset sum solver of Horowitz and Sahni.
And for this, we design a decomposition function, when applied to the ...
- 47
6
votes
1
answer
217
views
Lower bound for the OR problem
Let us have booleans $x_1, \cdots, x_n$. Any algorithm that determines $\bigvee_1^n x_i$ with probability at least $2/3$ requires $\Omega(n)$ time. It is not too difficult to prove this, but the proof ...
- 630
0
votes
0
answers
55
views
Finding the best $k-$subset which maximizes a matrix sum
Let $M\in \mathbb{R}^{N\times N}$ be a given matrix and $k\ge 2$ be a given integer. Then my question is the following optimization problem:
Is there a polynomial-time solution to the following ...
2
votes
0
answers
122
views
Asymptotic complexity lower bounds of proof checking
This paper on universal search mentions (on pp. 6-7) that proof checking can be done in $O(n^2)$ where $n$ is the length of the proof. Is this optimal? I don't want to specify the problem too ...
- 153
0
votes
1
answer
124
views
Complexity for universal Counter Machine with {0,1}-valued registers
Consider a universal $\{0,1\}$-$k$-counter machine where each of the $k$ registers has a value in $\{0,1\}$ (as opposed to any non-negative integer in the usual formulation), and there are states $q_1,...
- 1
1
vote
1
answer
51
views
Graph classes where giving a q-clique edge cover makes testing for q-colouring easy
A $q$-clique of a graph is a complete subgraph on $q$ vertices.
A $q$-clique edge cover of $G$ is a set of subgraphs of $G$ such that each subgraph is a $q$-clique and each edge of G is contained in ...
- 1,723
1
vote
0
answers
98
views
Additive error approximations of GapP functions
Consider a GapP function $g(x)$ for $x \in \{0, 1\}^{*}$. Consider an approximation $\tilde g(x)$ such that
\begin{equation}
\left|g(x) - \tilde g(x)\right| \leq \epsilon.
\end{equation}
Consider a ...
- 173
3
votes
1
answer
386
views
Fastest approximate triangle counting algorithms in dense graphs
One may compute the number of triangles in a graph by matrix multiplication in time $O(n^\omega)$. There is also a very simple algorithm that runs in time $O(n^3/(\epsilon^2 T))$ (where $T$ is the ...
- 630
1
vote
1
answer
58
views
Amortized time and worst case (non-amortized) separation
Assume a reasonable computation model (thinking about pointer machine or RAM model), is there a problem where there is a clear separation between amortized and worst case complexity? Say, if ...
- 235
13
votes
2
answers
270
views
Is the exponent in the rectangular matrix multiplication convex?
My question is regarding the paper "Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor". In the paper, the authors show an algorithm for multiplying a ...
- 630
0
votes
0
answers
25
views
Looking for information about a problem of a least subset of vectors modulo 2 summing to another vector [duplicate]
I'm quite interested in the following algorithmic problem, on which I can't find any information. Phrased as a decision problem:
Given a set of vectors $V$ in $\text{GF}(2)^n$, a vector $\mathbf u$ ...
9
votes
1
answer
223
views
Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$?
The Triangle Finding decision problem asks whether there exists a triangle in a graph $G$ containing $n$ vertices. A triangle is a triple of vertices $(a, b, c)$ such that $a$ is adjacent to $b$, $b$ ...
- 5,127
1
vote
1
answer
69
views
What is the run-time of the bin packing approximation algorithm?
The best approximation algorithm that I found for the bin packing problem is by Hoberg and Rothvoss (SODA, 2017). In their Theorem 1.2, they mention that their algorithm finds a solution with at most $...
- 2,078
2
votes
0
answers
98
views
Does the awards budget cut problem support a sub $O(n\log n)$ time solution?
There's a famous problem these days in the interview prep community (particularly in PRAMP) called the awards budget cut problem.
The problem gives you an input of $n$ integers called grants $g_1 ... ...
- 369
-1
votes
1
answer
428
views
What is the time complexity of computing intersection and union of Nondeterministic Finite Automata (NFAs)?
Assume that $\mathcal{A} = (Q_A, \Sigma, \Delta_A, q_{i_A}, F_A)$ and $\mathcal{B} = (Q_B, \Sigma, \Delta_B, q_{i_B}, F_B)$ are two NFAs. What is the worst-case time complexity of computing $\mathcal{...
- 157
1
vote
0
answers
217
views
Is there a known lower-bound on what the exponent could be, even if it turned out that P=NP?
Underlying motivation for the question: if someone showed that $\text{P}=\text{NP}$ but the algorithm thus produced for, e.g., $3\text{-SAT}$, runs in time $\Omega(n^G)$ where $G$ is Graham's number, ...
- 1,530
5
votes
2
answers
264
views
Can we recover integers $a_i$ from the sum $a_0 + a_1e+a_2e^2+\cdots+a_ne^n$?
Since $e$ is transcendental, the function $f:\mathbb Z_{\geq 0}^{n+1}\to \mathbb R$ is injective,
$$ f(\underset{\text{Integers}\ \geq\ 0}{\underbrace{a_0,a_1,\ldots, a_n}}) = a_0 + a_1e+a_2e^2+\cdots ...
- 1,959
6
votes
1
answer
339
views
Are all problems in the same time hierarchy related to each other?
In this problem, "runtimes" refer to worst-case complexity compared up to constant factor.
Say you have two problems, A and B, in the same time hierarchy, and it is clear that algorithm P ...
- 69
6
votes
0
answers
192
views
Computing the $n$-th bit of the binary representation of $\pi$
I (only) learned today about the following fact:
The $n$-th binary digit of $\pi$ is computable without calculating all the previous digits.
This apparently has been discovered in 1995, and follows ...
- 4,451
2
votes
0
answers
184
views
Schönhage-Strassen algorithm: why don't we work over $\mathbb{C}$
I am trying to understand how Schönhage-Strassen works for integers by studying von zur Gathen and Gerhard's Modern computer algebra. However they only talk about multiplication of polynomials.
In the ...
- 121
14
votes
1
answer
1k
views
Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?
Question: Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?
Background: I recently stumbled upon the ...
- 5,127
19
votes
1
answer
1k
views
Has parameterized complexity led to better algorithms?
I know that for the vertex cover problem, if we know that the parameter $k$ (which is the number of vertices in the solution) is small, then we can expect to solve it feasibly in practice. So far, ...
- 301
2
votes
1
answer
237
views
Is it possible to reduce an NP language to a NEXP language with exponentially smaller input length?
Suppose we have an NP-complete language $L_1$ and a NEXP-complete language $L_2$.
For any deterministic exptime machine $M_1$ with oracle access $M_1^{L_1}$, is it possible to find a deterministic ...
- 383
1
vote
1
answer
93
views
Can a NEXP machine simulate invalid queries to a promise problem oracle?
Let $A=(A_{YES},A_{NO})$ be some promise problem (such as xSAT, the Local Hamiltonian problem, etc). Suppose we want to show that a P machine with access to a the oracle A can always have its output ...
- 383
-4
votes
1
answer
33
views
Big O question concerning time complexity
Why is O(f(n)) − O(f(n)) not equal to 0? Full disclosure this is a question from practice problems for my theory class.
- 1
1
vote
0
answers
88
views
Find all paths between specially paired nodes in a DAG in linear time
If I have a DAG with 2n nodes partitioned into n pairs of nodes with e edges, is there a ...
- 916
1
vote
0
answers
122
views
Bounds on the construction of regular expressions' intersection operator
There are references on the exponential worst-case of the intersection operator for regular expressions (see [1]). However, I was wondering if there are similar results for the construction process ...
user59861
2
votes
1
answer
114
views
Complexity of acyclicity of a "nondeterministic" graph
By "nondeterministic" I mean the graph is a collection of sets of "candidate" edges sharing a single destination: $E \subseteq 2^V \times V$. The problem is whether it is possible ...
- 123
24
votes
12
answers
3k
views
What are some algorithms where space complexity tends to be the limiting factor in practice?
Time complexity can't be any lower than space complexity (at least one operation is required to use a unit of memory), so what are some algorithms where space actually tends to be the limiting factor? ...
- 401
5
votes
1
answer
277
views
What's the constant coefficient of the Coppersmith-Winograd algorithm?
Every source I can find just says "too big to be practical."
- 401
2
votes
0
answers
172
views
Time complexity of Succinct-CVP
I want to know what is the best known lower time complexity of Succinct-CVP?
The succinct version of many P-complete problems are EXP-complete and Succinct-CVP is EXP-complete too (It is because of ...
- 327
3
votes
2
answers
198
views
Complexity of Set Difference
Given $k$ sets $S_1$, $S_2$, $\dots$, $S_k$ in the universe $U = \{1, 2, \dots, n\}$, is there a way to preprocess the $k$ sets such that there is an output-sensitive query algorithm that computes $...
- 31
6
votes
2
answers
539
views
Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis
In the recent question 3SUM Complexity—A special(?) Case I asked about why the set size $O(n^3)$ was an interesting value for the 3SUM Problem and got a nice answer. My reference was the paper “...
- 2,070
6
votes
2
answers
419
views
3SUM Complexity—A special(?) Case
In the paper “Consequences of Faster Alignment of Sequences” by
Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann which appeared in ICALP 2014 and is available here the following version of ...
- 2,070
3
votes
0
answers
133
views
Graph problems in P with unknown lower bounds
I am looking for references to interesting graph problems, which are known to be in P, but their precise big-O lower bounds are elusive. I would split this into 2 classes:
problems, where we know of ...
- 900
3
votes
0
answers
341
views
Fastest known algorithm to enumerate k-cliques in a graph for fixed k
Is the best known algorithm for finding all $k$-cliques in a graph with $n$ nodes, for a fixed $k$, given by https://theory.stanford.edu/~virgi/combclique-ipl-g.pdf ?
The time-complexity of the ...
- 209
2
votes
0
answers
85
views
Complexity of computing Earth Mover's Distance when the costs satisfy the triangle inequality
Let p and q by two categorical probability distributions over $\{1,2,...,k\}$. Given a set of costs $c_{ij} \ge 0, i,j \in \{1,2,...,k\}$ that satisfy the triangle inequality, that is $c_{ij} \le c_{...
- 201
10
votes
0
answers
177
views
Is 4-in-a-row PSPACE-complete?
This paper by Laurens Kuiper shows that axis-parallel k-in-a-row is PSPACE-complete in complexity for k ≥ 5, but leaves the question open for k = 4. Has there been any research progress on this ...
- 652
4
votes
2
answers
344
views
What are those deterministic algorithms for k-SAT that are not derandomization of random algorithms like PPSZ and Schöning's local search?
I am doing a survey on k-SAT where time complexity is in terms of n, i.e. the number of variables in a formula.
As for the fast algorithms for k-SAT, we see
biased-PPSZ, PPSZ, Schöning's local search,...
- 490
0
votes
1
answer
1k
views
Time complexity for multiplying two lower triangular matrices
I was wondering, if multiplication of two $n \times n$ lower (or upper) triangular matrices has a more efficient algorithm than multiplication of two general $n \times n$ matrices?
$$
\begin{bmatrix}
...
- 141
5
votes
0
answers
141
views
Program size versus program running time
Short "naive" question:
Is it true that faster algorithms require longer programs ?
Given a decision problem $A$ and a reasonable model of computation, there can be many ways (algorithms) ...
- 22.6k
1
vote
1
answer
114
views
Running an algorithm for fixed amount of time on RAM model machine
Suppose there is a deterministic algorithm of size $O(1)$ that operates on an input of size $N$ on a RAM model machine. I want to run the algorithm for $O(\sqrt{N})$ time, pause the algorithm, print "...
- 1,177
2
votes
0
answers
120
views
Is PP invariant under changing its cut-off from 1/2 to another number?
Suppose I have a fixed family of quantum circuits $\{C_i\}$ for which determining whether the maximum output acceptance probabilities are $p\geq 1/2$ or $p< 1/2$ is PP-hard.
Now suppose I have the ...
- 383
0
votes
0
answers
113
views
Are there complexity theory consequences of the collapse NEXP=EXP^NP?
It is clear that $NEXP\subseteq EXP^{NP}$, as a TM with exponential run time can simply query the NP oracle with an exponentially long query. However, it's not clear that the reverse $EXP^{NP}\...
- 383
2
votes
1
answer
178
views
Complexity of solving systems of linear equations with hash preimages
Introduction: I'm researching a decision problem that I thought was in NP because there are certificates for its instances that have a polynomial number of elements. However, I realized that there are ...
- 31
1
vote
0
answers
26
views
Sorting using comparisons that are not simple mappings of simple comparisons
The Python language has a sort(x) function that sorts a list based on the intrinsic comparison operator associated with the type of the elements of its input list x. One can also provide a cmp ...
- 201
5
votes
2
answers
402
views
Are there problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under nearly linear time reductions?
Background
It can be challenging to find computational problems that are solvable in $DTIME(n^k) - DTIME(n^{k-1})$ where $k \geq 2$.
Although some natural problems are known to exist, many of them ...
- 5,127