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.)
395
questions
10
votes
1
answer
716
views
Fastest known algorithm for finding simple paths through given set of vertices
For an undirected graph $G$ and a given set $S$ of vertices, what is the asymptotically fastest known algorithm for finding a simple path containing
all elements of $S$. What if we require the path to ...
- 103
13
votes
2
answers
889
views
Complexity of Membership-Testing for finite abelian groups
Consider the following abelian-subgroup membership-testing problem.
Inputs:
A finite abelian group $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ with arbitrary-...
0
votes
3
answers
1k
views
What is the problem in "closest pair problem" if all points share the same x-coordinate
The closest pair of points problem deals with the task to find a pair of points with the global minimum distance. There is a problem, when all points share the same x-coordinate, or at least a large ...
- 11
14
votes
1
answer
797
views
Is Quasi-polynomial time in PSPACE?
I had done some search on this but I was not able to find an answer either way.
Huck answered it fully. Thanks :)
- 2,579
7
votes
1
answer
320
views
Trade off between time and query complexity for total functions
This is a continuation of an earlier question on the trade off between time and query complexity. By a trade off we consider the following two types of algorithms:
The best query algorithm: this ...
- 10.2k
5
votes
1
answer
532
views
Consequences of a $O^*(2^{n / \log(n \log n)} )$ algorithm for a #P-complete problem
Question
Suppose that there exist a deterministic algorithm for solving a #P-complete problem in time $O^*(2^{n / \log(n \log n)})$. What would be the theoretical consequences of such a fact? ...
- 6,780
-1
votes
3
answers
758
views
Examples for $\Theta(n^n)$ problems
I was just wondering if there is a problem whose best solution (under common assumptions) has time complexity $\Theta(n^n)$. And what complexity class would that belong to?
- 351
18
votes
2
answers
7k
views
Complexity of computing the discrete Fourier transform?
What is the complexity (on the standard integer RAM) of computing the standard discrete Fourier transform of a vector of $n$ integers?
The classical algorithm for fast Fourier transforms, ...
- 23.1k
7
votes
3
answers
1k
views
Complexity lower bound for regular languages
Suppose I have a regular language $L$, and I would like to lower-bound the complexity of deciding membership in $L$. Suppose I know that the minimal DFA for $L$ has $N$ states.
I would like to claim ...
- 10.3k
2
votes
1
answer
458
views
Arthur-Merlin protocol with BQP power
Context: Aaronson raised the following question:
Let f be a black-box function, which is promised either to satisfy the
Simon promise or to be one-to-one. Can a prover with the power of BQP
...
- 185
4
votes
0
answers
327
views
Time complexity for solving linear congruences?
What is the best known algorithm to solve linear congruences of the form below?
$$a x + b \equiv 0 \space (n)$$
And what is the time complexity of it?
- 41
23
votes
3
answers
808
views
Adding integers represented by their factorization is as hard as factoring? Reference request
I'm looking for a reference for the following result:
Adding two integers in the factored representation is as hard as factoring two integers in the usual binary representation.
(I'm pretty sure ...
- 36.9k
16
votes
1
answer
531
views
Can you decide equivalence for monotone Boolean expressions that do not contain negation in PTIME?
Is the following problem in PTIME, or coNP-hard:
Given two Boolean expressions $e_1$ and $e_2$ in variables $x_1,\dots,x_n$, without negation (ie, the expressions are entirely built up via $\wedge$ ...
- 288
18
votes
3
answers
1k
views
Trade off between time and query complexity
Working directly with time complexity or circuit lower bounds is scary. Hence, we develop tools like query complexity (or decision-tree complexity) to get a handle on lower bounds. Since each query ...
- 10.2k
-4
votes
2
answers
353
views
Examples of uncommon problems with different asymptotic costs?
I've being studying some topics of Discrete Mathematics, and I found only a few examples of problems with uncommon asymptotic costs, like Θ(sqrt(n)) or Θ(log(n)) beyond the obvious ones (binary search,...
- 1
5
votes
1
answer
178
views
A notion of time for uniform circuits
Let C={Cn} be a family of uniform boolean circuits, whose size and depth are bounded by functions s(n) and d(n).
What is the upper bound on the running time of a Turing machine M that evaluates C? ...
- 463
19
votes
5
answers
1k
views
Why do relational databases work at all, given the theoretical exponential complexity of answer finding (in the size of the query)?
It seems to be known that to find an answer to a query $Q$ over a relational database $D$, one needs time $|D|^{|Q|}$, and one cannot get rid of the exponent $|Q|$.
As $D$ can be very large, we wonder ...
6
votes
0
answers
247
views
Restricted Reachability Problem
Let $G$ be a directed acyclic graph with $V$ vertices and $E$ edges. Choose some subset of $n\leq V$ "special" vertices $\{v_i\}_{i=1}^n$. How efficiently can we preprocess $(G, \{v_i\})$ so that we ...
- 800
13
votes
6
answers
617
views
Any algorithmic problem has a time complexity dominated by counting?
What I refer to as counting is the problem that consists in finding
the number of solutions to a function. More precisely, given a
function $f:N\to \{0,1\}$ (not necessarily black-box), approximate
$\#...
- 960
16
votes
2
answers
6k
views
What is the fastest algorithm to compute rank of a rectangular matrix?
Given an $m \times n$ matrix (assuming $m \ge n$), what is the fastest algorithm to compute its rank and basis of the columns?
I am aware it can be solved through linear matroid intersection, which ...
- 163
2
votes
3
answers
291
views
Explaining input-size of integral arguments to undergraduate CS students
When I teach undergraduate algorithms, the students have no problem accepting that two n-bit numbers can be added in $O(n)$ time, or that modular exponentiation takes $O(n^3)$ time.
But when we get ...
- 1,003
10
votes
2
answers
657
views
What happens if we improve the time hierarchy theorems?
In a nutshell, the time hierarchy theorems say that a Turing machine can solve more problems if it has more time for computation. In detail for deterministic TM and time-constructable functions $f,g$ ...
- 1,338
11
votes
3
answers
1k
views
Can Merlin convince Arthur about a certain sum?
Merlin, who has unbounded computational resources, wants to convince Arthur that
$$m|\sum_{p\le N,\ p\text{ prime}}p^k$$
for $(N,m,k)$ with $k=O(\log N)$ and $m=O(N).$ Computing this sum in the ...
- 1,737
19
votes
4
answers
3k
views
What is the "right" definition of upper and lower bounds?
Let $f(n)$ be the worst case running time of a problem on input of size $n$. Let us make the problem a bit weird by fixing $f(n) = n^2$ for $n=2k$ but $f(n) = n$ for $n=2k+1$.
So, what is the lower ...
- 331
14
votes
3
answers
2k
views
Lower Bounds for Data Structures
Are results known which rule out the existence of "too-good-to-be-true" data structures?
For example: can one add $Split$ and $Join$ functionality to an order maintenance data structure (see Dietz ...
- 800
3
votes
0
answers
602
views
Another weird $O(N \log{N})$ Turing machine
This is another question related to the (still open) nice question "Alphabet of single-tape Turing machine" by Emanuele Viola. I describe the question very informally (perhaps it has a trivial ...
- 22.6k
10
votes
1
answer
314
views
Is this language recognizable by a 3 symbols TM in O(n log n)?
I was playing with the very interesting and still open question "Alphabet of single-tape Turing machine" (by Emanuele Viola) and came up with the following language :
$L = \{ x \in \{0,1\}^n \text{ s....
- 22.6k
8
votes
0
answers
259
views
For median is it optimal to compare in pairs first?
Median can be done in linear time and is now down to (I think) $2.97n$.
The lower bounds is (I think) $(2+\epsilon)n$ where $\epsilon$ is very small.
The following theorem, if true, may help improve ...
- 549
15
votes
4
answers
3k
views
Counting the number of vertex covers: when is it hard?
Consider the #P-complete problem of counting the number of vertex covers of a given graph $G = (V, E)$.
I'd like to know if there is any result showing how the hardness of such problem varies with ...
- 6,780
12
votes
1
answer
3k
views
Complexity of converting a boolean circuit to a boolean formula
Given a boolean circuit $C$ on $n$ variables (which uses just NOT,AND and OR gates), what is the most efficient way to extract the boolean formula represented by the circuit? Is there a polytime ...
- 1,344
5
votes
2
answers
607
views
Is qsort linear when sorting only two values?
This CodeGolf answer suggests that quick sorting an array whose elements can take only two values is linear. Can this assumption be proved?
- 696
6
votes
2
answers
1k
views
Do runtimes for P require EXP resources to upper-bound? … are concrete examples known? (answer: yes and yes)
Update #6:
Wow, quick service on TCS StackExchange! Emanuele Viola has provided an answer Are runtime bounds in P decidable? Answer: No.
Emanuele's answer illuminates (for me) Luca Trevisan's ...
- 1,506
7
votes
2
answers
360
views
Complexity of summing up integral powers
Let $x$ be a rational number, and $S_n(x)= \sum_{1\leq i\leq n} i^x$. What is the complexity of computing $S_n(x)$ correct to $d$ decimal places? Is this a Hard problem?
It is clear from Faulhaber's ...
- 521
13
votes
2
answers
2k
views
Reversing a list using two queues
This question is inspired by an existing question about whether a stack can be simulated using two queues in amortized $O(1)$ time per stack operation. The answer seems to be unknown. Here is a more ...
- 1,458
8
votes
2
answers
836
views
What is the initialization time of a link-cut tree?
Link-cut tree is a data structure invented by Sleator and Tarjan, which supports various operations and queries on a $n$-node forest in time $O(\log n)$. (For example, operation link combines two ...
- 7,638
11
votes
2
answers
4k
views
Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix
This is a specialized version of a previous question:
Complexity of Finding the Eigendecomposition of a Matrix .
For NxN symmetric matrices, it is known that O(N^3) time suffices to compute the ...
- 111
46
votes
8
answers
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 ...
- 11.9k
65
votes
10
answers
12k
views
One Stack, Two Queues
background
Several years ago, when I was an undergraduate, we were given a homework on amortized analysis. I was unable to solve one of the problems. I had asked it in comp.theory, but no ...
- 16.5k
10
votes
1
answer
1k
views
Quickly finding empty-string producing nonterminals in a CFG
For a given context free language G, we call a nonterminal $A_i$ nullable if $A_i \rightarrow^* \epsilon$, ie we can derive the empty string from $A_i$ after applying a finite number of productions.
...
- 4,670
5
votes
1
answer
504
views
What is the running time of taking a limit?
I'm interested in finding the running time(s) for determining mathematical limits.
For instance, $\lim_{x \to 2} \frac{1}{x} = \frac{1}{2}$.
I'd like to know more about algorithms for determining ...
- 2,100
22
votes
1
answer
1k
views
Binary multiplication and parity convolution
This question is about the relationship between normal multiplication of binary numbers and polynomial multiplication mod 2. To make the question concrete, I would ideally like to know if there is a ...
- 3,950
22
votes
2
answers
883
views
Multiplicative version of 3-SUM
What is known about the time complexity of the following problem, which we call 3-MUL?
Given a set $S$ of $n$ integers, are there elements $a,b,c\in S$ such that $ab=c$?
This problem is similar to ...
- 321
8
votes
1
answer
552
views
Analysis of the synergy of two algorithms in comparison to their simulation in parallel
Consider the following two algorithms for searching in a sorted array of $n$ elements:
A) interpolation search and binary search simulated in parallel, and
B) search through alternating ...
- 2,733
0
votes
2
answers
5k
views
Linked List size in constant time or linear time [closed]
The space-time complexity of getting the size of the linked list can differ in different implementations as far as I understand it.
In the Boost C++ library one finds that the size() function can be ...
- 111
44
votes
7
answers
5k
views
Using lambda calculus to derive time complexity?
Are there any benefits to calculating the time complexity of an algorithm using lambda calculus? Or is there another system designed for this purpose?
Any references would be appreciated.
- 2,233