Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
5 votes
3 answers
183 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 ...
Matei Chesa's user avatar
0 votes
0 answers
55 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 ...
apirogov's user avatar
  • 101
-1 votes
1 answer
82 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 ...
Sanyo Mn's user avatar
-1 votes
1 answer
187 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}$. ...
S. M.'s user avatar
  • 109
3 votes
1 answer
391 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 ...
A. H.'s user avatar
  • 133
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: ...
rus9384's user avatar
  • 355
0 votes
0 answers
47 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 ...
Enk9456's user avatar
1 vote
1 answer
83 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 ...
Changxin Cao's user avatar
0 votes
0 answers
115 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, ...
EXPTIME-complete's user avatar
2 votes
1 answer
96 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 ...
delete000's user avatar
  • 828
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 ...
Wenhao Wu's user avatar
4 votes
1 answer
506 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 ...
Erel Segal-Halevi's user avatar
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\...
Junqiang Peng's user avatar
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,...
deb2014's user avatar
2 votes
0 answers
46 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 ...
rivana's user avatar
  • 65
1 vote
0 answers
52 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 ...
rivana's user avatar
  • 65
4 votes
0 answers
106 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$$...
templatetypedef's user avatar
1 vote
1 answer
123 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, ...
roignoirewg's user avatar
6 votes
1 answer
266 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|)$: $...
agemO's user avatar
  • 187
4 votes
1 answer
290 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 ...
Colonizor48's user avatar
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 ...
user70015's user avatar
-3 votes
1 answer
108 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 ...
aeet's user avatar
  • 1
-2 votes
1 answer
143 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?
Janet Stewart's user avatar
1 vote
0 answers
171 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. ...
Souvik's user avatar
  • 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. ...
Cybernetic's user avatar
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 ...
rus9384's user avatar
  • 355
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 ...
rus9384's user avatar
  • 355
13 votes
2 answers
374 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 ...
FxMySz's user avatar
  • 131
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 ...
white's user avatar
  • 1
-2 votes
1 answer
257 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 ...
Marion's user avatar
  • 183
7 votes
0 answers
188 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 ...
Manuel Eberl's user avatar
1 vote
0 answers
37 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. ...
Erel Segal-Halevi's user avatar
1 vote
0 answers
55 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 ...
Naysh's user avatar
  • 686
4 votes
1 answer
187 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 ...
Erel Segal-Halevi's user avatar
4 votes
1 answer
360 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: ...
Sebastian Szczepański's user avatar
6 votes
0 answers
89 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 ...
QMath's user avatar
  • 303
4 votes
1 answer
176 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 ...
fiktor's user avatar
  • 141
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 ...
QMath's user avatar
  • 303
2 votes
1 answer
119 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 ...
QMath's user avatar
  • 303
-3 votes
1 answer
100 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 ...
user68029's user avatar
0 votes
0 answers
136 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^...
Nicholas Brandt's user avatar
2 votes
0 answers
63 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 ...
user43464's user avatar
  • 209
2 votes
0 answers
40 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 ...
user76284's user avatar
  • 662
2 votes
1 answer
81 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 ...
Dmytro Taranovsky's user avatar
3 votes
1 answer
112 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 ...
user76284's user avatar
  • 662
1 vote
1 answer
261 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 ...
WangAtChicago's user avatar
0 votes
1 answer
224 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 ...
Bapcap's user avatar
  • 21
0 votes
1 answer
220 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 ...
LLL's user avatar
  • 101
-1 votes
1 answer
150 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=...
NoteMyQuestion's user avatar
1 vote
1 answer
549 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 ...
E. Turok's user avatar

1
2 3 4 5
9