Questions tagged [time-complexity]

Time complexity of decision problems or relations among time-bounded complexity classes. (Use [tag:analysis-of-algorithms] for the time taken by particular algorithms.)

Filter by
Sorted by
Tagged with
12
votes
5answers
1k views

Are there decidable problems for which for no algorithm we can give time bounds?

Are there decidable problems such that for no algorithm which solves the problem we can give a time bound as a function of the length n of the input instance? I arrived at this question because I was ...
7
votes
3answers
643 views

Different definitions of complexity

I'm a math student and have encountered the concept of (mainly time) complexity of algorithms in several courses so far (Analysis of Algorithms, Cryptography, Numerical Analysis). However what strikes ...
6
votes
1answer
350 views

Solving multiple instances of 3SUM generated from the same set

(this is a follow-up of my previous question, which uses the 3SUM' problem instead of 3SUM) Suppose we have a list $S$ of $n$ integers. Usually, for 3SUM, we only determine if there exist $a$,$b$,$c$ ...
7
votes
0answers
253 views

Complexity of reachability in Markov Chains

Is anything known about the complexity of the following problem beyond membership in PTIME: Given a finite Markov chain $M$, an initial state $q_0$ and a set $F$ of (absorbing) states, is the ...
10
votes
1answer
681 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 ...
12
votes
2answers
754 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
2answers
627 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 ...
13
votes
1answer
684 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 :)
7
votes
1answer
275 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 ...
5
votes
1answer
506 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? ...
-1
votes
3answers
749 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?
18
votes
2answers
6k 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, ...
6
votes
3answers
946 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 ...
2
votes
1answer
391 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 ...
4
votes
0answers
281 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?
22
votes
3answers
779 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 ...
16
votes
1answer
446 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$ ...
18
votes
3answers
679 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 ...
-4
votes
2answers
347 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,...
5
votes
1answer
157 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? ...
19
votes
5answers
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 ...
6
votes
0answers
240 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 ...
13
votes
6answers
566 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 $\#...
14
votes
1answer
4k 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 ...
2
votes
3answers
280 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 ...
10
votes
2answers
548 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$ ...
11
votes
3answers
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 ...
19
votes
4answers
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 ...
14
votes
3answers
1k 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 ...
3
votes
0answers
588 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 ...
10
votes
1answer
275 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....
8
votes
0answers
249 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 ...
14
votes
4answers
2k 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 ...
10
votes
1answer
2k 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 ...
5
votes
2answers
565 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?
6
votes
2answers
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 ...
7
votes
2answers
305 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 ...
12
votes
2answers
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 ...
8
votes
2answers
754 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 ...
9
votes
1answer
2k 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 ...
40
votes
6answers
13k 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 ...
60
votes
10answers
10k 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 ...
8
votes
1answer
896 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. ...
5
votes
1answer
494 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 ...
22
votes
1answer
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 ...
22
votes
2answers
832 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 ...
8
votes
1answer
540 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 ...
0
votes
2answers
3k 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 ...
43
votes
7answers
3k 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.