The tag has no wiki summary.

learn more… | top users | synonyms

20
votes
4answers
1k 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. ...
3
votes
2answers
108 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 ...
6
votes
2answers
258 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 ...
20
votes
1answer
565 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 ...
9
votes
1answer
369 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 ...