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
4
votes
0answers
271 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
759 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
422 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
619 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
154 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
239 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
562 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
3k 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
540 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
2k 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
585 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
298 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
746 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
12k 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 ...
59
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
886 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
493 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
969 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
808 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
539 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.