Tag Info

Hot answers tagged time-complexity

Accepted

Has parameterized complexity led to better algorithms?

There are several examples of problems where a parameterized algorithm performs well in practice. Let me mention two such problems. In the $k$-Path problem where we are looking for a simple path of ...
Accepted

How "hard" is it to maximize a polynomial function subject to linear constraints?

Your problem is NP-hard, even for polynomials of degree 2. The crucial reference is Theodore Motzkin and Ernst Strauss (1965) "Maxima for graphs and a new proof of a theorem of Turan" ...
• 5,782
Accepted

What is a natural problem in theory of computation?

To be clear, it's not meant to be formalizable. It's not a theorem, it's an observation about the world -- it's okay if "natural" is subjective here. For analogy, if someone says "differentiation is ...
• 7,738

What are some algorithms where space complexity tends to be the limiting factor in practice?

Most computations in algebraic geometry / commutative algebra. Most involve computing Grobner bases, which are EXPSPACE-hard in general. There are some parameter regimes where this improves and thus ...
• 37.8k
Accepted

Equivalent formulation of complexity theory in Lambda Calculus?

As you point out, the λ-calculus has a seemingly simple notion of time-complexity: just count the number of β-reduction steps. Unfortunately, things are not simple. We should ask: ...
• 11.5k

Data structure to determine if sets are disjoint in o(n) time

The communication complexity of the set disjointness problem is $\Omega(n)$. The communication complexity is a lower bound on the time complexity of testing whether the two instances are disjoint. ...
• 12.3k
Accepted

Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?

This CSP is known to be SETH-hard. More precisely, assuming SETH, for any constant $\varepsilon > 0$ there is no $d^{(1-\varepsilon)n}$-time algorithm for solving this CSP with domain size $d$. ...
• 5,023
Accepted

questions on implications Babais quasi P time graph isomorphism result

Johnson graphs are actually easy to recognize. In particular, you can recognize whether an input graph is a Johnson graph in polynomial time, and you can construct an isomorphism between two ...
• 14.5k

Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?

It depends on the precise definition of RAM being used, but (for most reasonable definitions of RAMs) this would also imply that SAT is not solvable in $O(n^{2-e})$ time by multitape TMs, a ...
• 27.5k

Lower-bounds under SETH

Most problems need at least linear time, so $O(n \log n)$ may be a little too close to optimal for a SETH based lower bound, generally we want running times where one can improve on the exponent by ...
• 27.5k

Are there any problems whose best known algorithms have running time $n^{\log \log n}$?

The best-known deterministic algorithm for testing polynomial identities given by depth-three diagonal circuits has running time $n^{O(\log \log n)}$ [1]. More explicitly, we are given an expression ...

Quantum polynomial hierarchy vs counting hierarchy

I was quite surprised as well to not find this hierarchy in the literature, so I wrote my graduate thesis about it. It will be available online soon, at which point I will update this answer with a ...
• 2,099
Accepted

Does $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) = \mathrm{DTIME}(n^{2+o(1)})$?

Here is a counterexample, i.e. a language with an $O(n^{2+ε})$ algorithm (using multitape Turing machines) for every $ε>0$, but not uniformly in $ε$: Accept $0^k 1^m$ iff $k>0$ and the $k$th ...
• 2,577
Accepted

Are space and time hierarchies even comparable?

You can get the situation you describe by choosing weird functions $f(n)$ and $g(n)$. For example, let $g(n) = n^3$ and f(n) = \begin{cases} n & \text{if $n$ is odd}, \\\ 2^{n^5} & \text{...
• 2,873

Is there a non-deterministic version of the complexity class PP?

PP is defined as a probabilistic class and we don't normally think of nondeterministic versions of any of these classes (as far as I'm aware). In a sense probabilistic classes and nondeterministic ...
• 7,738
Accepted

Determining if a word of specific length exists that is not accepted by a NFA

Your problem is NP-hard, by reduction from 3SAT. Let $\varphi$ be a 3SAT formula with $m$ clauses and on the $n$ variables $x_1,\dots,x_n$. Construct a NFA over the alphabet $\Sigma=\{0,1\}$ as ...
• 12.3k
Accepted

Formalization of proofs and computational complexity paradox?

$\def\mc{M_\mathit{const}}\def\mp{M_\mathit{paradox}}$Let me for the record write up the answer to Q1, so that it doesn’t live only in the comments. The reasoning given in steps 1–5 in the question ...
• 18.2k
Accepted

Is there a non-deterministic version of the complexity class PP?

It does not really make sense to define an “X-version of class Y”, this is a misguided viewpoint. You define classes because they are useful or interesting in whatever context you are investigating, ...
• 18.2k

Equivalent formulation of complexity theory in Lambda Calculus?

Counting $\beta$-reductions is one kind of complexity measure for $\lambda$-calculus, but a more flexible and reasonable one is cost semantics, where the operational semantics is augmented by various ...
• 29.3k
Accepted

Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?

Adding to Sasha's answer. Roughly speaking, BBH posits that every property of functions that is hard to decide with only query access to the function (black box access) is also hard to decide when you'...
• 27.5k
Accepted

Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis

I think currently it is not even known if strong ETH and 3SUM are related, see e.g. [1]. For the relation of ETH and 3SUM, note that ETH really cannot be refuted by improving polynomial time ...
• 1,831

Are there any problems whose best known algorithms have running time $n^{\log \log n}$?

The best-known algorithm for testing isomorphism of finite groups whose solvable radical is either (a) contained in the center or (b) elementary abelian, is $n^{O(\log \log n)}$. These are, ...
• 37.8k

What are the computations model with a constant slowdown ? (and why do we care about Turing machines)

For any fixed k > 1, the k-tape Turing machine model has a universal Turing machine with only linear slow down. This is a result due to Martin Fürer: The Tight Deterministic Time Hierarchy. STOC ...
• 2,271
Accepted

Can emptiness of reversal-bounded counter languages be decided in time polynomial to the number of counters?

If the number of counters or the number of reversals (or both) is part of the input, the problem becomes coNP-complete (unless there is exactly one counter): The upper bound was shown by Hague and ...
Accepted

NEXPTIME-completeness with more time for reductions

The trouble with exponential-time reductions is that they may exponentially expand the input, and this leads to all sorts of weirdness. So, to begin with, neither EXP nor NEXP is closed under exp-time ...
• 18.2k

Definition of near-linear algorithm

A natural definition of "near-linear" should be: A function $f:\mathbb{N}\to\mathbb{N}$ is near-linear, if $~f(n)\in O(n^{1+\varepsilon})~$ for all $\varepsilon>0$.
• 5,782

"Almost sorting" integers in linear time

This sounds a lot like the ASort algorithm. See this article by Giesen et. al.: https://www.inf.ethz.ch/personal/smilos/asort3.pdf Unfortunately, the running time is not quite linear. The article ...
• 181
Accepted

Is counting simple cycles in $P$ for graphs of bounded tree width?

A simple cycle is a connected set where every vertex has degree 2. Then you have a formula SC(X) stating X (a set of edges) is a simple cycle. You can see many versions of Courcelle's theorem for ...
• 1,046
In knowledge compilation, the task is to compile some set $A\subseteq \{0,1\}^n$ into a format such that various queries can then be answered in polynomial time. For example, you can "compile&...