Most Popular
1500 questions
19
votes
6 answers
Which models of computation can be expressed through grammars?
This is a reformulation of Are grammars programs? previous asked by Vag and with many suggestions from the commenters.
In what way can a grammar be seen as specifying a model of computation?
If, for example, we take a simple context-free grammar…
Rehno Lindeque
- 677
- 4
- 13
19
votes
5 answers
Why do relational databases work at all, given the theoretical exponential complexity of answer finding (in the size of the query)?
It seems to be known that to find an answer to a query $Q$ over a relational database $D$, one needs time $|D|^{|Q|}$, and one cannot get rid of the exponent $|Q|$.
As $D$ can be very large, we wonder why databases work at all in practice.
Is it…
imz -- Ivan Zakharyaschev
- 363
- 3
- 12
19
votes
2 answers
Balls and Bins analysis in the m >> n regime
It's well known that if you throw n balls into n bins, the most loaded bin is highly likely to have $O(\log n)$ balls in it. In general, one can ask about $m > n$ balls in $n$ bins. A paper from RANDOM 1998 by Raab and Steger explores this in some…
Suresh Venkat
- 32,071
- 4
- 95
- 271
19
votes
3 answers
Classification of Typed/Untyped Lambda Calculi
Can anyone explain briefly (if thats possible!) or refer me to a reference, summarizing the differences between untyped lambda calculus and the more common typed lambda calculi?
I'm particularly looking for statements of their expressive power,…
jon_darkstar
- 293
- 2
- 7
19
votes
4 answers
What is the "right" definition of upper and lower bounds?
Let $f(n)$ be the worst case running time of a problem on input of size $n$. Let us make the problem a bit weird by fixing $f(n) = n^2$ for $n=2k$ but $f(n) = n$ for $n=2k+1$.
So, what is the lower bound of the problem? The way I understood it is…
Wei Yu
- 331
- 2
- 3
19
votes
5 answers
Why doesn't P=NP imply P=AP (i.e. P=PSPACE)?
It is well known that if $\mathbf{P}=\mathbf{NP}$ then the polynomial hierarchy collapses and $\mathbf{P}=\mathbf{PH}$.
This can easily be understood inductively using oracle machines.
The question is - why can't we continue the inductive process…
Joseph
- 387
- 2
- 6
19
votes
0 answers
Are theoretical computer science conferences losing touch with reality?
Anonymous account for obvious reasons. I am a researcher in TCS. I have several publications in SODA/STOC/FOCS. I've recently been so disgruntled with the way these conferences are run, and wanted to voice my frustration into the void. It seems like…
DisgruntledTCSResearcher
- 331
- 3
19
votes
1 answer
What are the limits of computation in this universe?
I understand that Turing completeness requires unbounded memory and unbounded time.
However there is a finite amount of atoms in this universe, thus making memory bounded. For example even though $\pi$ is irrational there is no way to store more…
Good Person
- 393
- 1
- 5
- 9
19
votes
3 answers
Integrality gap and approximation ratio
When we consider an approximation algorithm for a minimization problem, the integrality gap of an IP formulation for this problem gives a lower bound of an approximation ratio for certain class of algorithms (such as rounding or primal-dual…
Snowie
- 1,200
- 7
- 10
19
votes
2 answers
Is there a Time Hierarchy theorem for PH?
Is it true that there are problems in the polynomial hierarchy solvable in time $O(n^k)$ (by an alternating Turing machine in some level of the polynomial hierarchy) that are not solvable in $O(n^{k-1})$ in any level of the polynomial hierarchy?
In…
Joseph
- 387
- 2
- 6
19
votes
1 answer
Has parameterized complexity led to better algorithms?
I know that for the vertex cover problem, if we know that the parameter $k$ (which is the number of vertices in the solution) is small, then we can expect to solve it feasibly in practice. So far, this is the only example I've seen on Downey, Rodney…
Felipe
- 301
- 1
- 5
19
votes
5 answers
P with integer factorization oracle
I just read the "Is integer factorization an NP-complete problem?" question ... so I decided to spend some of my reputation :-) asking another question $Q$ having $P(\text{Q is trivial}) \approx 1$:
If $A$ is an oracle that solves integer…
Marzio De Biasi
- 22,915
- 2
- 58
- 127
19
votes
4 answers
Problems that are counter-intuitively solvable in practice?
Recently, I went through the painful fun experience of informally explaining the concept of computational complexity to a young talented self-taught programmer, who never took a formal course in algorithms or complexity before. Not surprisingly, a…
Konstantinos Koiliaris
- 836
- 1
- 8
- 17
19
votes
1 answer
Is equivalence of unambiguous context-free languages decidable?
It is well known that the equivalence problem is undecidable for general context-free languages. However, all proofs of this fact that I am aware of seem to involve some ambiguous context-free grammars. For this reason, I would like to ask if it is…
Jára Cimrman
- 464
- 2
- 8
19
votes
0 answers
Why is the Pumping Lemma sometimes called Bar-Hillel's Lemma?
There are several papers in the literature that refer to the Pumping Lemma for context free languages as Bar-Hillel's Lemma (for example, here, here, and on the Wikipedia page). However, the first article to prove the result was only co-authored by…
Vince Vatter
- 319
- 1
- 9