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.)
404
questions
3
votes
2
answers
75
views
Why is order/choice an issue for a logic for PTIME
As I'm reading on the question of a logic for PTIME and in particular about CPT and its variants, whilst things make sense and I follow along, I came to realise that I don't fundamentally understand ...
- 833
0
votes
0
answers
54
views
Why can't we just reduce from Bounded HALT to Bounded PCP?
We know that:
PCP is famously undecidable (as it can encode any DTM), but
Bounded-HALT (DTM on some input halts in at most k steps) is EXPTIME-complete, and
Bounded-PCP (there is a matching ...
- 101
4
votes
1
answer
281
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 ...
- 353
-1
votes
1
answer
79
views
The role of Turing machines in computational complexity [closed]
In the popular book "Introduction to algorithms" by CLRS even though rigorous proofs are given about the complexity analysis of algorithms there is no mention of Turing machines. Instead ...
- 384
4
votes
1
answer
173
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 ...
CommunityBot
- 1
-1
votes
1
answer
185
views
Calculation on Sparsification and critical clauses in SAT
I followed from this question.
I need to prove, the final result $s_k \leq (1 − \Omega(k^{−1}))s_{\infty}.$
But before prove the final result first I need to prove the $s_k \leq (1 − d/k))s_{\infty}$.
...
- 109
1
vote
1
answer
82
views
Algorithm for Shortest Path in a DAG with Multiple Transportation Modes and Associated Setup Costs
I am working on a problem involving finding the shortest path in a Directed Acyclic Graph (DAG), where each edge's cost depends on multiple transportation modes, each with its own setup cost. I am ...
CommunityBot
- 1
3
votes
1
answer
386
views
Time complexity of PPZ algorithm
I am trying to understand PPZ (Paturi, Pudlák, Zane) derandomization algorithm for k-SAT, it seems to be very difficult for me. The last line in the below of the image, I don't understand the time ...
- 17.4k
0
votes
0
answers
45
views
Computational complexity of LambdaMART
Could someone provide a general estimate of the average (time) complexity of the LambdaMART learning-to-rank algorithm?
A particular implementation of LambdaMART is known as XGBRanker. It uses ...
- 1
7
votes
0
answers
113
views
Parameterized complexity of factoring
When multiplying integer numbers $A$ and $B$, one can use a 0-1 matrix to represent one of the multiplication steps. For example, given numbers (written in binary) $A=1101$ and $B=1011$ the matrix is:
...
- 6,470
3
votes
1
answer
307
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:
...
CommunityBot
- 1
0
votes
0
answers
113
views
Complexity of, given any elementary function $f$ and a natural $n$, compute $n$ digits of $f(x)$
We define problem $A$ as follows. Each instance of the problem consists of:
(a) some succinct codification of an elementary function, that is, a function constructed by composing arithmetic operators, ...
- 408
2
votes
1
answer
93
views
Maximum cardinality disjoint cycle cover in undirected graphs
I call a maximum cardinality disjoint cycle cover of a graph a vertex-disjoint cycle cover containing the maximum possible number of cycles in the graph. What is known about the complexity of this ...
- 1,316
3
votes
0
answers
89
views
What's the complexity of the "decision version" of counting the paths in a graph?
I learned that "counting the simple paths in a graph(whether directed or not)" is #P-Complete.
I'm wondering what the complexity is for its decision version.
Here are two types I'm ...
- 31
4
votes
1
answer
505
views
Deciding whether a convex region is empty
Let $S\subseteq \mathbb{R}^n$ be a convex region defined by $$g_i(x)\leq 0, ~~i\in 1,\ldots,m,$$ where $g_i$ are convex functions.
The goal is to decide whether $S$ is empty, and if not - find a point ...
- 2,222
10
votes
2
answers
404
views
The complexity of finding a Borsuk-Ulam point
The Borsuk-Ulam theorem says that for every continuous odd function $g$ from an n-sphere into Euclidean n-space, there is a point $x_0$ such that $g(x_0)=0$.
Simmons and Su (2002) describe a method ...
- 14k
17
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\...
- 3,698
0
votes
0
answers
94
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,...
- 122
2
votes
0
answers
45
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 ...
- 65
1
vote
0
answers
51
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 ...
- 65
4
votes
0
answers
105
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,242
1
vote
1
answer
122
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, ...
- 17.4k
14
votes
3
answers
3k
views
What is a natural problem in theory of computation?
In Stephen Cook's paper on the P vs NP problem,[1] he states the following [2]:
Feasibility Thesis: A natural problem has a feasible algorithm iff it has a polynomial-time algorithm.
My question ...
- 271
6
votes
1
answer
251
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
0
votes
0
answers
68
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 ...
2
votes
4
answers
6k
views
Complexity of greedy coloring
I was looking at some heuristics for coloring and found this book on Google books: Graph
Colorings By Marek Kubale
They describe the Greedy algorithm as follows:
...
- 1
-3
votes
1
answer
107
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
133
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?
- 384
1
vote
0
answers
165
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
93
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. ...
- 804
1
vote
0
answers
131
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 ...
- 355
13
votes
2
answers
373
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 ...
- 6,470
2
votes
0
answers
45
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 ...
- 355
0
votes
0
answers
51
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
247
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 ...
- 1,083
14
votes
2
answers
1k
views
Gaussian Elimination in terms of Group Action
Gaussian elimination makes determinant of a matrix polynomial-time computable. The reduction of complexity in computing the determinant, which is otherwise sum of exponential terms, is due to ...
CommunityBot
- 1
7
votes
0
answers
181
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
36
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,222
4
votes
1
answer
186
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 ...
- 321
1
vote
0
answers
51
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 ...
- 606
46
votes
8
answers
21k
views
Complexity of Finding the Eigendecomposition of a Matrix
My question is simple:
What is the worst-case running time of the best known algorithm for computing an eigendecomposition of an $n \times n$ matrix?
Does eigendecomposition reduce to matrix ...
- 121
6
votes
0
answers
86
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
3
votes
0
answers
73
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
118
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 ...
- 17.4k
-3
votes
1
answer
98
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 ...
- 679
0
votes
0
answers
135
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
1
answer
80
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,577
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 ...
- 662
3
votes
1
answer
110
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 ...
- 6,999