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.)
389
questions
-1
votes
0
answers
55
views
Introduction to complexity calculation
I want to understand how is the probability of each input is distributed / defined, because it looks so abstract for me, for example here is a question write an algorithm to calculate the median of 3 ...
5
votes
1
answer
169
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|)$:
$...
- 153
3
votes
1
answer
134
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 ...
- 271
0
votes
0
answers
58
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
91
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
83
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
124
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
81
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
119
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
366
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
203
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
170
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
31
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,046
1
vote
0
answers
41
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
170
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,046
1
vote
1
answer
196
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
80
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
124
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
68
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
46
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
95
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
128
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^...
- 171
2
votes
0
answers
57
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 ...
- 651
2
votes
1
answer
60
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
104
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 ...
- 651
1
vote
1
answer
192
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
210
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
200
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
110
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
348
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
342
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$
...
- 129
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
324
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
266
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
231
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
103
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,046
2
votes
0
answers
79
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
38
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(...
- 451
1
vote
1
answer
145
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
108
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
54
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