# 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.)

396 questions
Filter by
Sorted by
Tagged with
60 views

### would statistical randomness disprove P=NP

I saw a proof that claimed if the 3sat problem was statistically random which by definition means there are no patterns, then a deterministic turing machine could not possibly solve it more ...
1k views

150 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 ...
1 vote
228 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: ...
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 ...
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: ...
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 ...
88 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
135 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. ...
89 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. ...
1 vote
128 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 ...
371 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 ...
43 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 ...
48 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 ...
220 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 ...
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 ...
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 ...
1 vote
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. ...
181 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 ...
1 vote
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 ...
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 ...
82 views

### Time hierarchy for one-tape Turing machines

The time hierarchy for multitape Turing machines is tight (see ): 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 ...
70 views

### Time complexity of context-free languages

I am reading an old paper  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 ...
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 ...
48 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 ...
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, ...
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 ...
132 views

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?
349 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 ...
1 vote
415 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 ...
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$ ...