Most Popular
1500 questions
41
votes
2 answers
Semantic vs. Syntactic Complexity Classes
In his "Computational Complexity" book, Papadimitriou writes:
RP is in some sense a new and unusual kind of complexity class. Not any polynomially bounded nondeterministic Turing machine can be the basis of defining a language in RP. For a machine…
Sadeq Dousti
- 16,479
- 9
- 69
- 152
40
votes
14 answers
How practical is Automata Theory?
There is always a way for application in topics related to theoretical computer science. But textbooks and undergraduate courses usually don't explain the reason that automata theory is an important topic and whether it still has applications in…
Dark Templar
- 559
- 1
- 5
- 5
40
votes
3 answers
Is optimally solving the n×n×n Rubik's Cube NP-hard?
Consider the obvious $n\times n\times n$ generalization of the Rubik's Cube. Is it NP-hard to compute the shortest sequence of moves that solves a given scrambled cube, or is there a polynomial-time algorithm?
[Some related results are described in…
Jeffε
- 23,129
- 10
- 96
- 163
40
votes
10 answers
Data for testing graph algorithms
I am looking for a source of huge data sets to test some graph algorithm implemention. Please also provide some information about the type/distribution (e.g. directed/undirected, simple/not simple, weighted/unweighted) of the graphs in the source if…
Chris
40
votes
1 answer
Sorting algorithm, such that each element is compared $O(\log n)$ times, and doesn't depend on a sorting network
Are there any known comparison sorting algorithms that do not reduce to sorting networks, such that each element is compared $O(\log n)$ times?
As far as I know, the only way to sort with $O(\log n)$ comparison on each element is to construct an AKS…
Chao Xu
- 4,399
- 23
- 32
40
votes
5 answers
Results in Theoretical CS independent of ZFC
I'm going to ask a quite vague question, since the borderline between theoretical computer science and math is not always easy to distinguish.
QUESTION: Are you aware of any interesting result in CS which
is either independent of ZFC (i.e. standard…
OldFella
- 501
- 3
- 4
40
votes
3 answers
Selecting papers to read
DISCLAIMER: This is an open ended question and stackexchange puritans would probably feel an extraordinary urge to vote it down to oblivion. However, I cannot think of any other forum more appropriate and promising for getting answer to this…
Tathagata
- 565
- 3
- 6
40
votes
6 answers
Regular expressions aren't
Ask even someone with a background in computer science what a regular expression is, and the answer is likely to go beyond the constraint of being within reach of a finite-state automaton.
For example, the “regular…
Greg Bacon
- 639
- 7
- 16
40
votes
7 answers
How do I get started in theoretical CS ?
I'm a freshmen studying computer science and I already know that I want to go into academia with focus of theoretical comp sci. I already read some of papers referenced in this question and this question convinced me further.
What should I be doing…
Good Person
- 393
- 1
- 5
- 9
40
votes
1 answer
Importance of single author papers?
I'm a fourth year PhD student in theoretical computer science. I'd like to stay in academia, so I'm thinking about how best to advance my career. Obviously the best way to do that is write lots of good papers, but another question is whether I…
Student
- 329
- 2
- 4
40
votes
4 answers
Why does Coq have Prop?
Coq has a type Prop of proof irrelevant propositions which are discarded during extraction. What are the reason for having this if we use Coq only for proofs. Prop is impredicative, so Prop : Prop, however, Coq automatically infers universe indexes…
Konstantin Solomatov
- 1,762
- 11
- 20
40
votes
13 answers
Easy decision problem, hard search problem
Deciding whether a Nash equilibrium exists is easy (it always does); however, actually finding one is believed to be difficult (it is PPAD-Complete).
What are some other examples of problems where the decision version is easy but the search version…
Travis Service
- 902
- 7
- 14
40
votes
3 answers
Circuit lower bounds over arbitrary sets of gates
In the 1980s, Razborov famously showed that there are explicit monotone Boolean functions (such as the CLIQUE function) that require exponentially many AND and OR gates to compute. However, the basis {AND,OR} over the Boolean domain {0,1} is just…
Scott Aaronson
- 13,733
- 2
- 62
- 68
40
votes
1 answer
Prerequisite for learning GCT
It seems that Geometric Complexity Theory requires much knowledge of pure maths such as algebraic geometry, representation theory.
While I am a CS student and do NOT have classes of very abstract and pure mathematics, I am interested in this…
syucha
- 401
- 5
- 4
40
votes
7 answers
Applicability of Church-Turing thesis to interactive models of computation
Paul Wegner and Dina Goldin have for over a decade been publishing papers and books arguing primarily that the Church-Turing thesis is often misrepresented in the CS Theory community and elsewhere. That is, it is presented as encompassing all…
zenna
- 835
- 6
- 11