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

Filter by
Sorted by
Tagged with
2 votes
2 answers
180 views

Are there any problems whose best known algorithms have running time $n^{\log \log n}$?

It’s well known that problems such as integer factorization have running times contained in $e^{\text{Poly} \log }$ which is the same $n^{ \text{Poly} \log }$ (actually the log term is itself in a ...
user avatar
0 votes
0 answers
65 views

Number of outputs produced by levin search variant (SIMPLE)

Let $f$ be an inverting problem. If there is an algorithm A that invert $f$ in time $t(n)$, then the SIMPLE algorithm below invert $f$ in time $c.t(n)$ where $c$ is a constant depending only on $A$ ...
user avatar
-2 votes
0 answers
99 views

How do I convert a pseudo-polynomial algorithm to its equivalent exponential form?

I have a pseudo-polynomial algorithm that solves a decision problem $D$. How do I convert it in its "explicit" exponential form?
user avatar
  • 97
0 votes
1 answer
39 views

Selecting unique records from a large dataframe with many duplicate records

Suppose we have a dataframe with ~10M rows with ~9M duplicate records. What is the most time efficient way of selecting the unique records from this dataframe? Some sort of sampling algorithm?
user avatar
6 votes
1 answer
279 views

Lower-bounds under SETH

After reading a bit about SETH (the strong exponential time hypothesis), I see that a lot of lower bounds for problems in P can be proven if we assume SETH. But I notice that most of the ones that are ...
user avatar
  • 161
6 votes
1 answer
181 views

Solving All-Pairs Shortest Paths using a distance matrix in sub-cubic time

I'm working on a project centered around the All-Pairs Shortest Paths (APSP) problem. Common algorithms to APSP (Floyd-Warshall, Bellman-Ford, Johnson's) work with the standard definition of the ...
user avatar
  • 61
0 votes
0 answers
67 views

Simplify or bound using Big-O notation

I was following a research paper which have the following equation: $\left(1-\frac{1}{K}\right)^{K-i}\left[1-\left(1-\frac{1-p}{K}\right)^{i}\right]=\frac{i(1-p)}{K}+O\left(\left(\frac{i}{K}\right)^{2}...
user avatar
2 votes
0 answers
75 views

Nondeterministic polynomial time languages with linearly bounded certificates

Define the class $X$ of languages by the condition that a language $L$ over alphabet $\Sigma$ is in $X$ iff there are a constant $c > 0$ and a polynomial-time checking relation $R$ such that for ...
user avatar
  • 91
0 votes
0 answers
38 views

Does the linear algorithm of Farach for sorting suffixes imply a linear algorithm for sorting a special type of a sequence of integers?

I was looking at the lecture notes on a linear time suffix trie construction algorithm by Farach and I was wondering if his suffix sorting procedure implies anything about sorting integers.
user avatar
  • 1
4 votes
0 answers
88 views

Simulating a $k$ tape Turing machine with a 2 tape Turing machine

Let $k$ be an (fixed, $3$ for instance) integer, what is the fastest simulation of a $k$ tape Turing machine by a two tape Turing machine? That is we're looking for the best 2 tape TM $U$, such that ...
user avatar
  • 109
2 votes
0 answers
61 views

Can this relaxed subset-sum problem be solved with a smaller dynamic program? [closed]

Cross-post from CS.SE In the subset sum problem, the input is a list of positive integers $x_1,\ldots,x_n$ and an integer $T$, and the goal is to decide whether there is a subset of sum exactly $T$. ...
user avatar
2 votes
0 answers
41 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 ...
user avatar
1 vote
0 answers
29 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(...
user avatar
1 vote
1 answer
110 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 ...
user avatar
0 votes
0 answers
73 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 ...
user avatar
6 votes
1 answer
209 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 ...
user avatar
0 votes
0 answers
51 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 ...
user avatar
2 votes
0 answers
111 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 ...
user avatar
0 votes
1 answer
115 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,...
user avatar
  • 1
1 vote
1 answer
50 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 ...
user avatar
1 vote
0 answers
72 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 ...
user avatar
  • 153
3 votes
1 answer
187 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 ...
user avatar
1 vote
1 answer
56 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 ...
user avatar
  • 235
12 votes
2 answers
203 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 ...
user avatar
0 votes
0 answers
24 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$ ...
user avatar
9 votes
1 answer
214 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$ ...
user avatar
1 vote
1 answer
62 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 $...
user avatar
2 votes
0 answers
82 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 ... ...
user avatar
-1 votes
1 answer
253 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{...
user avatar
  • 157
1 vote
0 answers
215 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, ...
user avatar
5 votes
2 answers
253 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 ...
user avatar
6 votes
1 answer
335 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 ...
user avatar
  • 69
6 votes
0 answers
181 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 ...
user avatar
  • 4,331
2 votes
0 answers
147 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 ...
user avatar
14 votes
1 answer
850 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 ...
user avatar
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, ...
user avatar
  • 301
2 votes
1 answer
208 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 ...
user avatar
1 vote
1 answer
88 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 ...
user avatar
-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.
user avatar
  • 1
1 vote
0 answers
45 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 ...
user avatar
  • 916
1 vote
0 answers
116 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 ...
user avatar
2 votes
1 answer
110 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 ...
user avatar
  • 123
22 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? ...
user avatar
5 votes
1 answer
207 views

What's the constant coefficient of the Coppersmith-Winograd algorithm?

Every source I can find just says "too big to be practical."
user avatar
2 votes
0 answers
163 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 ...
user avatar
3 votes
2 answers
165 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 $...
user avatar
  • 31
6 votes
2 answers
489 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 “...
user avatar
  • 1,986
6 votes
2 answers
359 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 ...
user avatar
  • 1,986
3 votes
0 answers
126 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 ...
user avatar
  • 723
3 votes
0 answers
135 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 ...
user avatar
  • 189

1
2 3 4 5
8