Most Popular
1500 questions
44
votes
3 answers
Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time
It is commonly believed that for all $\epsilon > 0$, it is possible to multiply two $n \times n$ matrices in $O(n^{2 + \epsilon})$ time. Some discussion is here.
I have asked some people who are more familiar with the research whether they think…
Brian
- 541
- 4
- 6
44
votes
4 answers
Why have we not been able to develop a unified complexity theory of distributed computing?
The field of distributed computing has fallen woefully short in developing a single mathematical theory to describe distributed algorithms. There are several 'models' and frameworks of distributed computation that are simply not compatible with each…
Srikanth Sastry
- 645
- 4
- 9
44
votes
7 answers
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.
Shane
- 2,233
- 3
- 26
- 25
44
votes
2 answers
Do any quantum algorithms improve on classical SAT?
Classical algorithms can solve 3-SAT in $1.3071^n$ time (randomized) or $1.3303^n$ time (deterministic). (Reference: Best Upper Bounds on SAT )
For comparison, using Grover's algorithm on a quantum computer would look for and provide a solution in…
Alex Meiburg
- 827
- 6
- 15
44
votes
3 answers
P and NP classes explanation through lambda-calculus
In the introduction and explanation P and NP complexity classes often given through Turing machine.
One of the model of computation is the lambda-calculus.
I understand, that all of models of computation are equivalent (and if we can introduce…
Simplex
- 541
- 5
- 5
44
votes
8 answers
Rigour leading to insight
On MathOverflow, Timothy Gowers asked a question titled "Demonstrating that rigour is important". Most of the discussion there was about cases showing the importance of proof, which people on CSTheory probably do not need to be convinced about. In…
András Salamon
- 19,000
- 3
- 64
- 150
44
votes
7 answers
Truly random number generator: Turing computable?
I am seeking a definitive answer to whether or not generation of "truly random" numbers
is Turing computable. I don't know how to phrase this precisely.
This StackExchange question on "efficient algorithms for random number generation"
comes close…
Joseph O'Rourke
- 3,753
- 23
- 41
43
votes
6 answers
A probabilistic set with no false positives?
So, Bloom filters are pretty cool -- they are sets that support membership checking with no false negatives, but a small chance of a false positive. Recently though, I've been wanting a "Bloom filter" that guarantees the opposite: no false…
Christopher Monsanto
- 1,092
- 7
- 11
43
votes
2 answers
Alphabet of single-tape Turing machine
Can every function $f : \{0,1\}^* \to \{0,1\}$ that is computable in time $t$ on a single-tape Turing machine using an alphabet of size $k = O(1)$ be computed in time $O(t)$ on a single-tape Turing machine using an alphabet of size $3$ (say, $0,1,$…
Manu
- 7,659
- 3
- 37
- 42
43
votes
9 answers
References for TCS proof techniques
Are there any references (online or in book form) that organize and discuss TCS theorems by proof technique? Garey and Johnson do this for the various kinds of widget constructions needed for NP-completeness proofs (particularly in chapter 3 of…
Kurt
- 839
- 10
- 13
43
votes
8 answers
What do you do when you cannot make progress on the problem you have been working on?
I am a 2nd year graduate student in theory.
I have been working on a problem for the last year (in graph theory/algorithms).
Until yesterday I thought I am doing well (I was extending a theorem from a paper).
Today I realized that I have made a…
Kumar
- 2,044
- 13
- 27
43
votes
3 answers
What are the reasons that researchers in computational geometry prefer the BSS/real-RAM model?
Background
The computation over real numbers are more complicated than computation over natural numbers, since real numbers are infinite objects and there are uncountably many real numbers, therefore real numbers can not be faithfully represented by…
Kaveh
- 21,577
- 8
- 82
- 183
43
votes
3 answers
Consequences of a quasi-polynomial time algorithm for the graph isomorphism problem
The Graph Isomorphism problem (GI) is arguably
the best known candidate for an NP-intermediate problem.
The best known algorithm is sub-exponential algorithm
with run-time $2^{O(\sqrt{n \log n})}$.
It is known that GI is not…
Mohammad Al-Turkistany
- 20,928
- 5
- 63
- 149
43
votes
5 answers
The cozy neighborhoods of "P" and of "NP-hard"
Let $X$ be an algorithmic task. (It can be a decision problem or an optimization problem or any other task.) Let us call $X$ "on the polynomial side" if assuming that $X$ is NP-hard is known to imply that the polynomial hieararchy collapses. Let us…
Gil Kalai
- 6,033
- 35
- 73
43
votes
7 answers
Many-one reductions vs. Turing reductions to define NPC
Why do most people prefer to use many-one reductions to define NP-completeness instead of, for instance, Turing reductions?
Matthias
- 1,668
- 1
- 14
- 22