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

360 questions
Filter by
Sorted by
Tagged with
1 vote
124 views

### Computational complexity and general relativity

According to general relativity, the time that a Turing Machine near a massive object spends on computing every step is longer than the time that the Turing Machine far awayfrom a massive object ...
180 views

### What Complexity Class is this? Is this already known?

Let's call this the Path Game. For this example, lets imagine a 16x16 grid: Some of the squares in this grid are "deadly." If you step on it, you must restart and try to go over again. We ...
• 39
147 views

### list of 3-CNF formula that can be solved in polynomial time

Suppose i want to program a 3-SAT solver. I want my solver to first check whether a formula is in the list of 3-CNF that currently known can be solved in polynomial time before resorting to brute ...
• 101
51 views

• 99
76 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 ...
• 91
96 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 ...
• 109
70 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$. ...
• 1,826
47 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 ...
1 vote
29 views

• 1
1 vote
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,623
1 vote
78 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 ...
• 153
201 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 ...
• 600
1 vote
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 ...
• 235
219 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 ...
• 600
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$ ...
221 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$ ...
• 4,910
1 vote
62 views

282 views

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 216 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,500 5 votes 2 answers 257 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,754 6 votes 1 answer 337 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 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 ... • 4,361 2 votes 0 answers 152 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 ... 14 votes 1 answer 856 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 ... • 4,910 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 214 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 89 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 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 ... • 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 ). However, I was wondering if there are similar results for the construction process ... 2 votes 1 answer 112 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 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? ... • 381 5 votes 1 answer 224 views ### What's the constant coefficient of the Coppersmith-Winograd algorithm? Every source I can find just says "too big to be practical." • 381 2 votes 0 answers 164 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 ... 3 votes 2 answers 173 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
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 “...