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.)
395
questions
16
votes
2
answers
1k
views
Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?
The Constraint Satisfaction Problem I mentioned is similar to CNF-SAT: A variable can take values from some finite domain $D$ where $|D| = d$. A literal of variable $x$ is an expression of the form $x\...
- 163
0
votes
0
answers
92
views
Relationships between problem symmetry and its complexity
I read once that the more a problem has some symmetries the "easier" it is to solve and in particular its (time) complexity is polynomial.
Conversely, when starting from a polynomial problem,...
- 9
2
votes
0
answers
38
views
Does Goldreich-Levin algorithm for finding large Fourier coefficients have time complexity upper bound = sample complexity upper bound?
I'm currently working on finding better bounds for Goldreich-Levin algorithm for estimating large Fourier coefficients of a boolean function.
I was surprised seeing that the upper bounds for time ...
- 53
0
votes
0
answers
40
views
Computability of Time Complexity of Recursive Sets
Is every recursive set's worst-case time complexity a total recursive function?
0
votes
0
answers
31
views
Is there an efficient Goldreich-Levin algorithm that generalizes to agnostic PAC setting?
Goldreich Levin algorithm is an algorithm that based on some assumption (boundness on Fourier coefficients) outputs the indices for most significant Fourier coefficients of a boolean function, however ...
- 53
4
votes
0
answers
91
views
$\log^\star n$ is somewhat common in runtimes. Does the superroot ever make an appearance?
Many algorithms and data structures have iterated logarithms ($\log^\star n$) in their runtimes. This function is the discrete inverse of tetration, in that
$$\log_a^\star (a \uparrow \uparrow b) = b$$...
- 2,121
1
vote
1
answer
108
views
Complexity of analytic functions and integrals
There exist polynomial - time computable functions, log - space computable functions, and NC - functions. Given this:
To which class do analytic elementary functions, including trigonometric ones, ...
- 13
6
votes
1
answer
228
views
Fast algorithms for time bounded Kolmogorov complexity
For a universal Turing machine $U$, the time bounded Kolmogorov complexity of a string $x$ is silmilar to the usual Kolmogorov complexity but limited to programs $p$ running in time at most $t(|x|)$:
$...
- 187
3
votes
1
answer
146
views
is SUBEXP contained within PSPACE?, NP?
Let SUBEXP is the complexity class of all problems solvable in sub-exponential time in the length of the input. What are the known properties of this class? Is it known to be contained in PSPACE, if ...
- 321
0
votes
0
answers
63
views
What is the meaning of the additive epsilon term in the definition of a time constructible function?
There is a well-known theorem that states that a function $f$ is time constructible if and only if $f$ can be computed in time $O(f)$. But this theorem comes with some conditions: $f$ must be a ...
-3
votes
1
answer
96
views
Algebra in complexity theory
Recently an idea came to my mind. Suppose $V$ is vector space and $\dim V = n$. Then, since $V \simeq \mathbb{R}^n$, any conjunction of $n$ boolean formulas $\phi_1, \ldots, \phi_n$ about vectors from ...
- 1
-2
votes
1
answer
85
views
Polynomial vs. Exponential Time Complexity [closed]
Does $2^{log_2{n}}$ grow faster than a polynomial? I know that $2^{log_2{n}}$ can be simplified as $n$ but can it be considered as an exponential?
1
vote
0
answers
131
views
How "Algebrization" is "A New Barrier in Complexity Theory"?
Being an enthusiast in computational complexity theory, I recently came across with this wonderful work Algebrization: A New Barrier in Complexity Theory.
My question is about Theorem 5.3 in it (pp. ...
- 19
-1
votes
1
answer
86
views
How is memory being used by an algorithm, to define its space complexity? [closed]
In computation we always talk about the time and space complexity of a given algorithm. The time complexity describes how long an algorithm takes in relation to the quantity of input it receives. ...
- 99
1
vote
0
answers
124
views
Can "dense" SAT instances be solved in time $o(2^n)$?
By "dense" I mean instances in which the ratio of variables to clauses is below the critical threshold $2^k\ln2−\frac{(1+\ln2)}2+\epsilon_k$ for $k$-SAT. For general SAT, however, I suppose ...
- 245
2
votes
0
answers
42
views
Reducing the amount of alternations without exponentially increasing the runtime?
Let $\mathsf{AltTime}(g(n), f(n))$ denote the class of languages that are solvable by an alternating machine using $f(n)$ time and $g(n)$ alternations.
Is there anything known about the following ...
- 245
13
votes
2
answers
370
views
General collection with the current state of complexity bounds of well-known unsolved problems?
Most classical computer science problems are still open concerning the exact asymptotic algorithmic worst-case complexity required to solve them.
Is there any online collaborative wiki (or other ...
- 131
0
votes
0
answers
47
views
The complexity order of regret (especially in online reinforcement learning)?
In online reinforcement learning theory, how to judge the complexity order of regret, if there are two or more terms in there?
For example, the state space is $X$, the action space is $A$, the episode ...
- 1
-2
votes
1
answer
218
views
What is the reason to believe that quantum heuristic algorithms can solve NP-Complete problems?
There is an ever going trend to believe that a large number of NP-Complete or NP-Hard problems can be solved using quantum heuristics.
I have observed, a common trend, to take any sort of ...
- 183
7
votes
0
answers
171
views
Baker–Gill–Solovay Theorem: why $2^n/10$ steps?
Context
I'm teaching an introductory complexity theory course right now and although I work in adjacent areas, I'm not an expert on complexity theory myself, so I'm still in the process of working ...
- 273
1
vote
0
answers
32
views
What is the complexity of the "characteristic bisection" method?
The characteristic bisection method is an algorithm for finding approximate zeros of multi-dimensional functions. It is a generalization of the bisection method; it is described briefly here.
...
- 2,086
1
vote
0
answers
42
views
What are the fastest known parameterized algorithms for Grid Tiling?
Let $k$ and $n$ denote positive integers.
In the $k$-GridTiling problem, for every pair of indices $(i,j)\in \{1, \dots, k\}^2$ we get a subset $S_{ij}\subseteq \{1, \dots, n\}^2$ of pairs of the ...
- 576
4
votes
1
answer
180
views
Computing an approximate root of a two-dimensional monotone function
Let $f$ be a Lipschitz-continuous function from the square $[-1,1]^2$ to itself, satisfying the following conditions:
For all $y\in [-1,1]$: $~~~~f(-1,y)_1\leq 0\leq f(1,y)_1$, and $f(x,y)_1$ is ...
- 2,086
1
vote
1
answer
221
views
How do you achieve linear time complexity of greedy graph coloring?
In most resources I could find, greedy algorithm is described as follows:
for every vertex $v$, assign the minimal color not used by its neighbors.
The above could be implemented as:
...
6
votes
0
answers
82
views
Time hierarchy for one-tape Turing machines
The time hierarchy for multitape Turing machines is tight (see [1]): if $f(n)=o(g(n))$ and $f,g$ are well-behaved, then $\textrm{DTIME}(f(n))\subsetneq \textrm{DTIME}(g(n))$. However, for one-tape ...
- 303
4
votes
1
answer
148
views
What is the time complexity of fermionic Fourier transform?
Suppose $N = 2^L$ and we are interested in performing the following transformation a $\mapsto$ a_hat on arrays of $N$ complex ...
- 141
3
votes
0
answers
70
views
Time complexity of context-free languages
I am reading an old paper [1] about time complexity of context-free languages. The computational model is the standard one-tape Turing machine. It is written on page 377 without a proof that "we ...
- 303
2
votes
1
answer
115
views
Time complexity of computing homomorphic image
The class of regular languages $\textrm{REG}$ is closed under inverse homomorphisms. The class $\textrm{TIME}(n^k)$ of languages solvable by a one-tape TM is also closed under inverse homomorphisms ...
- 303
0
votes
0
answers
47
views
Complexity of XOR-Knapsack
Edit: Actually I should have been more careful. Maybe the optimal way to solve this is to approach it as a series of $k'-$XOR sum problems (Generalized birthday due to Wagner) for increasing $k'.$ And ...
- 2,070
0
votes
0
answers
23
views
Is there a theoretical runtime guarantee to eigen decomposition (up to some convergence distance)?
I'm familiar with the QR algorithm for eigen decomposition in symmetric matrices, which takes roughly O(n^3) time. But that O(n^3) only holds if you take a constant number of QR steps per eigenvalue, ...
- 101
-3
votes
1
answer
96
views
Why if non determinism adds no power at all to DFAs or to Turing machines, why is it that most people beleieve P != NP [closed]
During Theory of Computation or Automata Theory or the equivalent class at my University, I was shown that non deterministic and deterministic automata can solve the exact same set of problems, then ...
0
votes
0
answers
132
views
Savitch's theorem for time complexity
Is it known that an analog of Savitch's theorem for time complexity is impossible, or is this an open question?
More formally, is $\exists d\ \forall c : \mathsf{NTIME}(n^c) \subseteq \mathsf{DTIME}(n^...
- 223
2
votes
0
answers
62
views
computational complexity of sparse matrix powers
Given a sparse matrix $A$ with $nnz(A)$ denoting the number of non-zero entries in it. What is the computational complexity of computing $A^k$, for some positive integer $k$? As $k$ gets larger, I ...
- 209
2
votes
0
answers
39
views
Statements equivalent to strongly polynomial time linear programming
Say a problem is SPT iff it admits an SPT algorithm. What statements of interest are known to be equivalent to "LP is SPT"? Examples:
"linear feasibility solving is SPT" (due to ...
- 652
2
votes
1
answer
65
views
Complexity of reachability in fractal mazes with traps
Is reachability in fractal mazes with traps EXPTIME complete?
A fractal maze includes one or more copies of itself. For example, see the question Decidability of Fractal Maze or Puzzling ...
- 2,537
3
votes
1
answer
107
views
Strongly polynomial time algorithm for shortest convex combination
Problem: Let $S$ be a finite set of vectors. Let $C$ be their convex hull. Compute $\operatorname{argmin}_{x \in C} \|x\|$.
Reference 1 gives an algorithm for this problem that is finite-time (Section ...
- 652
1
vote
1
answer
215
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 ...
- 101
0
votes
1
answer
215
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 ...
- 21
0
votes
1
answer
203
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
-1
votes
1
answer
120
views
Unweighted bipartite $b$-Matching
Consider the following problem, of which I am pretty certain that it is polynomially solvable.
Given some arbitrary bipartite Graph $G=(L\cup R,E)$ and some vector $b\in\mathbb{N}^{|L|}$ with $\sum_{i=...
1
vote
1
answer
397
views
Does Dijkstra's algorithm run faster on a DAG?
I know that Dijkstra's algorithm generally runs in $O(E \log V)$ using a min-heap. And I know we can use dynamic programming to find the shortest path of a DAG in $O(V+E)$. However, I was wondering ...
- 13
5
votes
3
answers
348
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 ...
- 369
0
votes
0
answers
72
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$
...
- 139
0
votes
1
answer
54
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?
6
votes
1
answer
329
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 ...
- 161
6
votes
1
answer
297
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 ...
- 61
2
votes
0
answers
79
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 ...
- 191
4
votes
0
answers
277
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 ...
- 149
2
votes
0
answers
105
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$.
...
- 2,086
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