Most Popular
1500 questions
36
votes
5 answers
Complexity of testing for a value versus computing a function
In general we know that the complexity of testing whether a function takes a particular value at a given input is easier than evaluating the function at that input. For example:
Evaluating the permanent of a nonnegative integer matrix is #P-hard,…
Joshua Grochow
- 37,260
- 4
- 129
- 228
35
votes
3 answers
Type classes vs object interfaces
I don't think I understand type classes. I'd read somewhere that thinking of type classes as "interfaces" (from OO) that a type implements is wrong and misleading.
The problem is, I'm having a problem seeing them as something different and how that…
oconnor0
- 463
- 4
- 6
35
votes
3 answers
Given a weighted dag, is there an O(V+E) algorithm to replace each weight with the sum of its ancestor weights?
The problem, of course, is double counting. It's easy enough to do for certain classes of DAGs = a tree, or even a serial-parallel tree. The only algorithm I have found which works on general DAGs in reasonable time is an approximate one (Synopsis…
Ealdwulf
- 562
- 4
- 8
35
votes
3 answers
An Anthology of Complexity Assumptions
In the paper The Random Oracle Hypothesis Is False, the authors (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan, and Rohatgi) discuss the implications of the random-oracle hypothesis. They argue that we know very little about separations between…
Sadeq Dousti
- 16,479
- 9
- 69
- 152
35
votes
5 answers
Is there a stable heap?
Is there a priority queue data structure that supports the following operations?
Insert(x, p): Add a new record x with priority p
StableExtractMin(): Return and delete the record with minimum priority, breaking ties by insertion order.
Thus, after…
Jeffε
- 23,129
- 10
- 96
- 163
35
votes
6 answers
Code in Academic Papers
In my academic career, I've read quite a few academic papers on various computer science topics. Many of which involve an implementation and some assessment of that implementation, yet I have found that very few of them actually publish the code…
Kevin Dolan
- 473
- 4
- 4
35
votes
10 answers
Any fundamental papers in TCS which were found to be incorrect/wrong later?
I am asking this question out of curiosity.
I recently encountered this well-known paper on (published in 2009):
the hardness of Euclidean kmeans
The paper showed that the previous NP-hardness result (link) for the Euclidean k-means (discovered in…
Inuyasha Yagami
- 1,531
- 1
- 8
- 25
35
votes
3 answers
Turing Machine restrictions that render halting decidable
If one restricts Turing Machines to a finite tape (i.e., to use bounded space $S$),
then the halting problem is decidable, essentially because after a number of steps (which can be calculated from the number of states $Q$, and $S$, and the…
Joseph O'Rourke
- 3,753
- 23
- 41
35
votes
1 answer
$BQP$ vs $QMA$?
The central problem of complexity theory is arguably $P$ vs $NP$.
However, since Nature is quantum, it would seem more natural to consider the classes $BQP$ (ie decision problems solvable by a quantum computer in polynomial time, with an error…
Anthony Leverrier
- 987
- 7
- 16
35
votes
4 answers
Proofs that expose a deeper structure
The standard proof of the Chernoff bound (from the Randomized Algorithms textbook) uses the Markov inequality and moment generating functions, with a bit of a Taylor expansion thrown in. Nothing too difficult, but somewhat mechanical.
But there are…
Suresh Venkat
- 32,071
- 4
- 95
- 271
35
votes
3 answers
complexity of greatest common divisor (gcd)
Consider the following counting problem (or the associated decision problem): Given two positive integers encoded in binary, compute their greatest common divisor (gcd). What is the smallest complexity class this problem is contained in? Can you…
Felix Breuer
- 461
- 4
- 4
35
votes
5 answers
What are some good introductory books on type theory?
I'm recently studying Haskell and programming languages. Could someone recommend some books on type theory?
qazwsx
- 559
- 1
- 6
- 7
35
votes
17 answers
Hardness jumps in computational complexity?
Minimum bandwidth problem is to a find an ordering of graph nodes on integer line that minimizes the largest distance between any two adjacent nodes. A $k$-caterpillar is a tree formed from main path by growing edge-disjoint paths of length at most…
Mohammad Al-Turkistany
- 20,928
- 5
- 63
- 149
35
votes
1 answer
NP-Completeness of the decision problem for the generalized 15-puzzle
I am interested in the natural generalization of the famous 15-puzzle, where you have to slide blocks until you have sorted all given numbers (usally there is a gap of 1 block).
Now the generalization would be to extend the size of the puzzle from…
Listing
- 607
- 5
- 13
35
votes
3 answers
What is the Volume of Information?
This question was asked to Jeannette Wing after her PCAST presentation on computer science.
“From a physics perspective, is there a maximum volume of information we can have?” (a nice challenge question for the theoretical computer science…
Lance Fortnow
- 8,681
- 44
- 59