Questions tagged [worst-case]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
1 answer
112 views

Proof of SPFA's worst-case complexity?

I am trying to prove the worst-case asymptotic time complexity of the Shortest Path Faster Algorithm (SPFA). I know the complexity is the same as the "original" Bellman-Ford (BF) algorithm, ...
user avatar
  • 33
3 votes
0 answers
65 views

Worst to average case reductions for quantum complexity classes

I am studying worst to average case reductions for different complexity classes. Consider quantum complexity classes like QMA, QSZK, or QIP. Is it known or believed that these classes are amenable to ...
user avatar
  • 153
4 votes
0 answers
74 views

When was the dynamic array first used as an example for amortized analysis?

I'm writing a report on amortized analysis, and I'm using the example of a dynamic array to explain each method. I think it would be nice to add a reference to when this example was first used, as it ...
user avatar
1 vote
1 answer
133 views

Asymptotic time required to simulate a Turing machine M for k steps

Problem: Given an encoding of a Turing machine M and a natural number k as input, find the output of M (given a blank tape) after k steps. Wikipedia's page on EXPTIME-complete says it takes O(k) time ...
user avatar
4 votes
0 answers
183 views

Worst-Case and Average-Case running-time equal with universal p-distribution with kolmogorov-complexity any applications of this theory?

at the moment I'm reading "Gems of Theoretical Computer Science" from Schöning and Pruim. In Chapter 8 the book defines a "universal probability distribution" in a way that the Average-Case running-...
user avatar
  • 41
30 votes
3 answers
1k views

Did "Where the really hard problems are" hold up? What are current ideas on the subject?

I found this paper to be very interesting. To summarize: it discusses why in practice you rarely find a worst-case instance of a NP-complete problem. The idea in the article is that instances usually ...
user avatar
  • 403
6 votes
2 answers
484 views

How powerful is $ACC^0$ circuit class in average case?

We know that $NEXP$ is not in $ACC^0$ . Does the result that $NEXP$ is not in $ACC^0$ also hold in average case? That is given a boolean function in $NEXP$ is it known that for every input length $...
user avatar
  • 12.5k
-2 votes
1 answer
365 views

Are Graph and Group Isomorphism problems random self-reducible?

Are Graph and Group Isomorphism problems known to be random self-reducible? If so is there a good proof? Are there other non-trivial examples of random self-reducibility? Is there a good reference?
user avatar
  • 12.5k
14 votes
2 answers
4k views

What is worst case complexity of number field sieve?

Given composite $N\in\Bbb N$ general number field sieve is best known factorization algorithm for integer factorization of $N$. It is a randomized algorithm and we get an expected complexity of $O\Big(...
user avatar
3 votes
1 answer
147 views

Number of different longest common substrings

Given an alphabet $\Sigma$ of size $k$ and two strings $w_1,w_2\in \Sigma^n$ of length $n$. The longest common substring problem asks for a longest string in the set $A(w_1,w_2)$ of all common ...
user avatar
  • 490
22 votes
3 answers
2k views

Justifying asymptotic worst-case analysis to scientists

I've been working on on introducing some results from computational complexity into theoretical biology, especially evolution & ecology, with the goal of being interesting/useful to biologists. ...
user avatar
3 votes
2 answers
133 views

How well can we do with this variable assignment problem?

Given in this problem is a set of values $0 \le c_{a,b} < n$, where $0 \le a < n$ and $0 \le b < n$. The problem is to find the following sum as quickly as possible: $$\sum_{a,b}{c_{a,b}x^a ...
user avatar
  • 2,080
7 votes
2 answers
425 views

What are the current best upper bounds of #P?

#P is the class of counting problems for problems in NP. In other words, a solution to #P returns the number of solutions to a particular problem in NP. I'm wondering if there have been any studies ...
user avatar
  • 2,080
20 votes
1 answer
765 views

How close can we get to linear multiply, add, and compare (on integers)?

Accoring to K. W. Regan's article "Connect the Stars", he mentions at the end that it is still an open problem to find a representation of integers such that the addition, multiplication, and ...
user avatar
  • 2,080
9 votes
1 answer
2k views

What is the worst case of the randomized incremental delaunay triangulation algorithm?

I know that the expected worst-case runtime of the randomized incremental delaunay triangulation algorithm (as given in Computational Geometry) is $\mathcal O(n \log n)$. There is an exercise which ...
user avatar
  • 193