Most Popular
1500 questions
39
votes
5 answers
Is there a logic without induction that captures much of P?
The Immerman-Vardi theorem states that PTIME (or P) is precisely the class of languages that can be described by a sentence of First-Order Logic together with a fixed-point operator, over the class of ordered structures. The fixed-point operator…
András Salamon
- 19,000
- 3
- 64
- 150
39
votes
2 answers
Mulmuley's GCT program
It is sometimes claimed that Ketan Mulmuley's Geometric Complexity Theory is the only plausible program for settling the open questions of complexity theory like P vs. NP question. There has been several positive commentaries from famous complexity…
Anonymous
- 4,041
- 19
- 43
39
votes
2 answers
Han's $O(n \log\log n)$ time, linear space, integer sorting algorithm
Is anyone familiar with Yijie Han's $O(n \log\log n)$, linear space, integer sorting algorithm? This result appears in a fairly short paper (Deterministic sorting in $O(n \log\log n)$ time and linear space. J. Alg. 50:96–105, 2004) which basically…
Ari
- 522
- 4
- 9
39
votes
9 answers
What is the difference between non-determinism and randomness?
I recently heard this -
"A non-deterministic machine is not the same as a probabilistic machine. In crude terms, a non-deterministic machine is a probabilistic machine in which probabilities for transitions are not known".
I feel as if I get the…
user200
39
votes
3 answers
Does $VP \neq VNP$ imply $P \neq NP$?
As far as I understand, the geometric complexity theory program attempts to separate $VP \neq VNP$ by proving that the permament of a complex-valued matrix is much harder to compute than the determinant.
The question I had after skimming through the…
Benno
- 393
- 3
- 4
39
votes
16 answers
Everyday encounters with NP-complete problems
Mark Dominus collected a few examples of polynomial-time reductions from various NP-hard problems to “regular expression” matching. Envisioning polynomial-time verifications isn't an enormous leap.
How do you illustrate the class NP-complete to…
Greg Bacon
- 639
- 7
- 16
39
votes
8 answers
Formal notion for energy complexity of computational problems
Computational complexity includes the study of time or space complexity of computational problems. From the the perspective of mobile computing, energy is very valuable computational resource. So, Is there a well studied adaptation of Turing…
Mohammad Al-Turkistany
- 20,928
- 5
- 63
- 149
39
votes
7 answers
What do we know about provably correct programs?
The ever increasing complexity of computer programs and the increasingly crucial position computers have in our society leaves me wondering why we still don't collectively use programming languages in which you have to give a formal proof that your…
Alex ten Brink
- 4,680
- 25
- 48
39
votes
3 answers
Why are mod_m gates interesting?
Ryan Williams just posted his lower bound on ACC, the class of problems that have constant depth circuits with unbounded fan-in and gates AND, OR, NOT and MOD_m for all possible m's.
What's so special about MOD_m gates?
They allow one to simulate…
Dana Moshkovitz
- 10,979
- 1
- 50
- 77
39
votes
2 answers
How many distinct colors are needed to lower-bound the choosability of a graph?
A graph is $k$-choosable (also known as $k$-list-colorable) if, for every function $f$ that maps vertices to sets of $k$ colors, there is a color assignment $c$ such that, for all vertices $v$, $c(v)\in f(v)$, and such that, for all edges $vw$,…
David Eppstein
- 50,990
- 3
- 170
- 278
39
votes
4 answers
Techniques for showing that problem is in hardness "limbo"
Given a new problem in $\mathsf{NP}$ whose true complexity is somewhere between $\mathsf{P}$ and being NP-complete, there are two methods that I know of that might be used to prove that resolving this is difficult:
Show that the problem is…
Suresh Venkat
- 32,071
- 4
- 95
- 271
39
votes
12 answers
Books on automata theory for self-study
I need a finite automata theory book with lots of examples that I can use for self-study and to prepare for exams.
user1652
- 99
- 1
- 3
- 4
39
votes
9 answers
Efficient and simple randomized algorithms where determinism is difficult
I often hear that for many problems we know very elegant randomized algorithms, but no, or only more complicated, deterministic solutions. However, I only know a few examples for this. Most prominently
Randomized Quicksort (and related geometric…
adrianN
- 877
- 10
- 13
39
votes
9 answers
Optimal greedy algorithms for NP-hard problems
Greed, for lack of a better word, is good. One of the first algorithmic paradigms taught in introductory algorithms course is the greedy approach. Greedy approach results in simple and intuitive algorithms for many problems in P. More interestingly,…
Shiva Kintali
- 10,578
- 41
- 74
39
votes
3 answers
Is there a backup/replacement for the Complexity Zoo?
This is a non-technical question, but certainly relevant for the TCS community. If considered inappropriate, feel free to close.
The Complexity Zoo webpage (http://qwiki.stanford.edu/index.php/Complexity_Zoo) has certainly been of great service to…
Martin Schwarz
- 5,496
- 25
- 41