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
-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 ...
MOHAMED SALHI's user avatar
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|)$: $...
agemO's user avatar
  • 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 ...
Colonizor48's user avatar
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 ...
user70015's user avatar
-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 ...
aeet's user avatar
  • 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?
Janet Stewart's user avatar
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. ...
Souvik's user avatar
  • 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. ...
Cybernetic's user avatar
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 ...
rus9384's user avatar
  • 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 ...
rus9384's user avatar
  • 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 ...
FxMySz's user avatar
  • 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 ...
white's user avatar
  • 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 ...
Marion's user avatar
  • 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 ...
Manuel Eberl's user avatar
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. ...
Erel Segal-Halevi's user avatar
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 ...
Naysh's user avatar
  • 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 ...
Erel Segal-Halevi's user avatar
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: ...
Sebastian Szczepański's user avatar
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 ...
QMath's user avatar
  • 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 ...
fiktor's user avatar
  • 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 ...
QMath's user avatar
  • 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 ...
QMath's user avatar
  • 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 ...
kodlu's user avatar
  • 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, ...
mwlon's user avatar
  • 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 ...
user68029's user avatar
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^...
Nicholas Brandt's user avatar
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 ...
user43464's user avatar
  • 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 ...
user76284's user avatar
  • 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 ...
Dmytro Taranovsky's user avatar
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 ...
user76284's user avatar
  • 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 ...
WangAtChicago's user avatar
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 ...
Bapcap's user avatar
  • 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 ...
LLL's user avatar
  • 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=...
NoteMyQuestion's user avatar
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 ...
E. Turok's user avatar
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 ...
Sidharth Ghoshal's user avatar
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$ ...
Omid Yaghoubi's user avatar
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?
Timeguy322's user avatar
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 ...
Jova's user avatar
  • 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 ...
Koen's user avatar
  • 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 ...
Alberto's user avatar
  • 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 ...
ULechine's user avatar
  • 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$. ...
Erel Segal-Halevi's user avatar
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 ...
Ryoshun Oba's user avatar
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(...
Mengfan Ma's user avatar
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 ...
Timothy Schommer's user avatar
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 ...
John Seppard's user avatar
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 ...
user2316602's user avatar
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 ...
Samrat Mukhopadhyay's user avatar
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 ...
Mario Carneiro's user avatar

1
2 3 4 5
8