Most Popular
1500 questions
47
votes
7 answers
What constitutes denotational semantics?
On a different thread, Andrej Bauer defined denotational semantics as:
the meaning of a program is a function of the meanings of its parts.
What bothers me about this definition is that it doesn't seem to single out what is commonly thought of as…
Ohad Kammar
- 2,677
- 23
- 28
47
votes
5 answers
Are there Conservation Laws in Complexity Theory?
Let me start with some examples. Why is it so trivial to show CVP is in P but so hard to show LP is in P; while both are P-complete problems.
Or take primality. It is easier to show composites in NP than primes in NP (which required Pratt) and…
V Vinay
- 3,873
- 1
- 24
- 30
47
votes
10 answers
Kolmogorov complexity applications in computational complexity
Informally speaking, Kolmogorov complexity of a string $x$ is a length of a shortest program that outputs $x$. We can define a notion of 'random string' using it ($x$ is random if $K(x) \geq 0.99 |x|$) It is easy to see that most of strings are…
ilyaraz
- 1,569
- 18
- 33
47
votes
0 answers
Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?
If we assume the Exponential-Time Hypothesis, then there is no $2^{o(n)}$ algorithm for $n$-variable 3-SAT, and many other natural problems, such as 3-COLORING on graphs with $n$ vertices. Notice though that, in general, encoding the input for…
Michael Lampis
- 3,698
- 22
- 31
47
votes
5 answers
Positive topological ordering
Suppose I have a directed acyclic graph with real-number weights on its vertices. I want to find a topological ordering of the DAG in which, for every prefix of the topological ordering, the sum of the weights is non-negative. Or if you prefer…
David Eppstein
- 50,990
- 3
- 170
- 278
46
votes
4 answers
Approximation algorithms for Metric TSP
It is known that metric TSP can be approximated within $1.5$ and cannot be approximated better than $123\over 122$ in polynomial time.
Is anything known about finding approximation solutions in exponential time (for example, less than $2^n$ steps…
Alex Golovnev
- 2,247
- 1
- 20
- 23
46
votes
5 answers
Historical reasons for adoption of Turing Machine as primary model of computation.
It's my understanding that Turing's model has come to be the "standard" when describing computation. I'm interested to know why this is the case -- that is, why has the TM model become more widely-used than other theoretically equivalent (to my…
Evan
- 563
- 4
- 5
46
votes
10 answers
Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?
Real computers have limited memory and only a finite number of states.
So they are essentially finite automata.
Why do theoretical computer scientists use the Turing machines
(and other equivalent models) for studying computers?
What is the point…
Rahul
- 627
- 1
- 5
- 8
46
votes
8 answers
Obituaries of dead conjectures
I am looking for conjectures about algorithms and complexity that were viewed credible by many at some point in time, but later they were either disproved, or at least disbelieved, due to mounting counter-evidence. Here are two examples:
Random…
Andras Farago
- 11,396
- 37
- 70
46
votes
4 answers
Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?
This is a question related to this one. Putting it again in a much simpler form after a lot of discussion there, that it felt like a totally different question.
The classical proof of the undecidability of the halting problem depends on…
Mohammad Alaggan
- 1,812
- 18
- 29
46
votes
8 answers
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 multiplication or are the best known algorithms…
Lev Reyzin
- 11,968
- 13
- 63
- 103
46
votes
3 answers
Wikipedia-style explanation of Geometric Complexity Theory
Can someone provide a concise explanation of Mulmuley's GCT approach understandable by non-experts? An explanation that would be suitable for a Wikipedia page on the topic (which is stub at the moment).
Motivation: I am "co-reading" Scott…
Alessandro Cosentino
- 4,000
- 35
- 43
46
votes
12 answers
Applications of representation theory of the symmetric group
Inspired by this question and in particular the final paragraph of Or's answer, I have the following question:
Do you know of any applications of the representation theory of the symmetric group in TCS?
The symmetric group $S_n$ is the group of…
Sasho Nikolov
- 18,189
- 2
- 67
- 115
44
votes
4 answers
Why would one ever use an Octree over a KD-tree?
I have some experience in scientific computing, and have extensively used kd-trees for BSP (binary space partitioning) applications. I have recently become rather more familiar with octrees, a similar data structure for partitioning 3-D Euclidean…
Noldorin
- 857
- 1
- 9
- 12
44
votes
4 answers
How would I go about learning the underlying theory of the Coq proof assistant?
I'm going over the course notes at CIS 500: Software Foundations and the exercises are a lot of fun. I'm only at the third exercise set but I would like to know more about what's happening when I use tactics to prove things like forall (n m : nat),…
user788