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

312 questions
Filter by
Sorted by
Tagged with
34 views

### 3SUM Complexity—A special(?) Case

In the paper “Consequences of Faster Alignment of Sequences” by Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann which appeared in ICALP 2014 and is available here the following version of ...
320 views

### Most general setting for fine-grained exponential-time complexity classes?

Consider the class of functions computable in time $(b+o(1))^n = 2^{\log_2{(b)} \times n + o(n)}$ on a $2$-tape Turing machine. By the Hennie-Stearns theorem, the same functions are computable in ...
47 views

### Probabilistic exponential time [closed]

Is it somewhat explored the exponential time complexity of bounded error probabilistic algorithms? Is there a name for the exponential analogue of BPP? In particular I wonder if it can be proved that ...
33 views

### How to determine if given “complex” time complexity is O(n^2)?

If a time complexity, for example or or , is not determinable by just looking at it whether is it in class O(n^2) or not, how do I decide? If a time complexity is given, and in it there are more ...
102 views

### Graph problems in P with unknown lower bounds

I am looking for references to interesting graph problems, which are known to be in P, but their precise big-O lower bounds are elusive. I would split this into 2 classes: problems, where we know of ...
300 views

### How “hard” is it to maximize a polynomial function subject to linear constraints?

General Problem Suppose we have a multivariate polynomial function $f(\mathbf{x})$, and several linear functions $\ell_i(\mathbf{x})$. What is known about the complexity of solving the following ...
Is the best known algorithm for finding all $k$-cliques in a graph with $n$ nodes, for a fixed $k$, given by https://theory.stanford.edu/~virgi/combclique-ipl-g.pdf ? The time-complexity of the ...