All Questions
1,636
questions
141
votes
30
answers
25k
views
Problems Between P and NPC
Factoring and graph isomorphism are problems in NP that are not known to be in P nor to be NP-Complete. What are some other (sufficiently different) natural problems that share this property? ...
271
votes
39
answers
143k
views
What Books Should Everyone Read?
[Timeline]
This question has the same spirit of what papers should everyone read and what videos should everybody watch. It asks for remarkable books in different areas of theoretical computer ...
485
votes
72
answers
182k
views
What papers should everyone read?
This question is (inspired by)/(shamefully stolen from) a similar question at MathOverflow, but I expect the answers here will be quite different.
We all have favorite papers in our own respective ...
232
votes
60
answers
97k
views
Major unsolved problems in theoretical computer science?
Wikipedia only lists two problems under "unsolved problems in computer science":
P = NP?
The existence of one-way functions
What are other major problems that should be added to this list?
Rules:
...
73
votes
9
answers
11k
views
Are runtime bounds in P decidable? (answer: no)
The question asked is whether the following question is decidable:
Problem Given an integer $k$ and Turing machine $M$ promised to be in P, is the runtime of $M$ ${O}(n^k)$ with respect to input ...
- 1,506
96
votes
9
answers
20k
views
What would it mean to disprove Church-Turing thesis?
Sorry for the catchy title. I want to understand, what should one have to do to disprove the Church-Turing thesis? Somewhere I read it's mathematically impossible to do it! Why?
Turing, Rosser etc ...
user200
47
votes
3
answers
5k
views
An NP-complete variant of factoring.
Arora and Barak's book presents factoring as the following problem:
$\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$
They add, further ...
- 3,946
36
votes
2
answers
5k
views
Status of Impagliazzo's Worlds?
In 1995, Russell Impagliazzo proposed five complexity worlds:
1- Algorithmica: $P=NP$ with all the amazing consequences.
2- Heuristica: $NP$-complete problems are hard in the worst-case ($P \ne NP$) ...
- 20.8k
52
votes
20
answers
9k
views
NP-hard problems on trees
Several optimization problems that are known to be NP-hard on general graphs are trivially solvable in polynomial time (some even in linear time) when the input graph is a tree. Examples include ...
- 10.6k
45
votes
4
answers
4k
views
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 ...
- 1,802
50
votes
4
answers
14k
views
Is finding the minimum regular expression an NP-complete problem?
I am thinking of the following problem:
I want to find a regular expression that matches a particular set of strings (for ex. valid email addresses) and doesn't match others (invalid email addresses).
...
- 1,306
93
votes
14
answers
21k
views
What kind of mathematical background is needed for complexity theory?
I am currently an undergraduate student, bound to graduate this year. After graduation, I am considering to work towards a TCS master/PhD. I have begun wondering what fields of mathematics are ...
- 3,751
51
votes
9
answers
11k
views
Best Upper Bounds on SAT
In another thread, Joe Fitzsimons asked about "the best current lower bounds on 3SAT."
I'd like to go the other way: What's the best current upper bounds on 3SAT? In other words, what is the time ...
- 16.5k
41
votes
2
answers
4k
views
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 ...
- 16.5k
381
votes
92
answers
114k
views
Algorithms from the Book
Paul Erdős talked about the "Book" where God keeps the most elegant proof of each mathematical theorem. This even inspired a book (which I believe is now in its 4th edition): Proofs from the ...
69
votes
10
answers
9k
views
Are there any open problems left about DFAs?
After studying deterministic finite state automata (DFA) in undergrad, I felt they are extremely well understood. My question is whether there is something we still don't understand about them. I don'...
- 612
51
votes
4
answers
5k
views
What are the best current lower bounds on 3SAT?
What are the best current lower bounds for time and circuit depth for 3SAT?
- 13.6k
48
votes
4
answers
4k
views
Generalized Ladner's Theorem
Ladner's Theorem states that if P ≠ NP, then there is an infinite hierarchy of complexity classes strictly containing P and strictly contained in NP. The proof uses the completeness of SAT under many-...
- 18.9k
39
votes
7
answers
10k
views
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 ...
37
votes
5
answers
9k
views
NEXP-complete problems
There are tons of NP-complete problems around and sources collecting them, e.g. see the book by Garey and Johnson. I would be interested to see a list of NEXP-complete problems as well. Is there one ...
27
votes
1
answer
2k
views
Deciding emptiness of intersection of regular languages in subquadratic time
Let $L_1,L_2$ be two regular languages given by NFAs $M_1,M_2$ as input.
Assume we would like to check whether $L_1\cap L_2\neq \emptyset$. This can clearly be done by a quadratic algorithm which ...
- 9,438
155
votes
39
answers
47k
views
What videos should everybody watch?
Stanford University now has a Youtube channel, with free access to HD video of full courses on everything from dynamical systems to quantum entanglement. More conferences and workshops are ...
113
votes
7
answers
10k
views
Solid applications of category theory in TCS?
I've been learning a few bits of category theory. It certainly is a different way of looking at things. (Very rough summary for those who haven't seen it: category theory gives ways of expressing all ...
- 27.3k
107
votes
5
answers
24k
views
List of TCS conferences and workshops
I would like to ask for help in compiling a list of as many TCS-related conferences and workshops as possible. My main motivation for doing this is to plan possible blog coverage of more theory ...
47
votes
7
answers
7k
views
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 ...
- 2,667
42
votes
2
answers
2k
views
Are the problems PRIMES, FACTORING known to be P-hard?
Let PRIMES (a.k.a. primality testing) be the problem:
Given a natural number $n$, is $n$ a prime number?
Let FACTORING be the problem:
Given natural numbers $n$, $m$ with $1 \leq m \leq n$, ...
- 421
621
votes
6
answers
130k
views
What's new in purely functional data structures since Okasaki?
Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few:
IntMap (also invented by ...
- 8,911
123
votes
15
answers
19k
views
What Lecture Notes Should Everyone Read?
There has been several questions with the same scheme as this one:
What papers should everyone read
What books should everyone read
What are the recent TCS books whose drafts are available online
...
68
votes
17
answers
5k
views
Applications of TCS to classical mathematics?
We in TCS often use powerful results and ideas from classical mathematics (algebra, topology, analysis, geometry, etc.).
What are some examples of when it has gone the other way around?
Here ...
62
votes
13
answers
9k
views
Open problems on the frontiers of TCS
In the thread Major unsolved problems in theoretical computer science?, Iddo Tzameret made the following excellent comment:
I think we should distinguish between major open problems that are viewed ...
57
votes
18
answers
2k
views
Where and how did computers help prove a theorem?
The purposes of this question is to collect examples from theoretical computer science where the systematic use of computers was helpful
in building a conjecture that lead to a theorem,
falsifying a ...
43
votes
7
answers
7k
views
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?
- 1,658
43
votes
3
answers
4k
views
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 ...
- 21.5k
38
votes
7
answers
9k
views
Books on programming language semantics
I've been reading Nielson & Nielson's "Semantics with Applications", and I really like the subject. I'd like to have one more book on programming language semantics -- but I really can get only ...
- 982
33
votes
5
answers
2k
views
Programming languages for efficient computation
It is impossible to write a programming language that allows all machines that halt on all inputs and no others. However, it seems to be easy to define such a programming language for any standard ...
- 10.2k
28
votes
2
answers
1k
views
Finding a prime greater than a given bound
Is a deterministic polynomial-time algorithm known for the following problem:
Input: a natural number $n$ (in binary encoding)
Output: a prime number $p > n$.
(According to a list of open ...
- 751
25
votes
4
answers
3k
views
Proofs, Barriers and P vs NP
It is well known that any proof resolving the P vs NP question must overcome relativization, natural proofs and algebrization barriers. The following diagram partitions the "proof space" into ...
- 10.6k
21
votes
2
answers
2k
views
Problem in BPP but not known to be in RP or co-RP
Is there an example of a natural problem that's in BPP but that's not known to be in RP or co-RP?
- 6,970
19
votes
1
answer
689
views
Looking for a nice problem inside SC but not in the first two levels
The complexity zoo doesn't have much about the $\mathsf{SC}$. I am looking for a nice$^\dagger$ problem that is in higher levels of the hierarchy, i.e. a problem in $\mathsf{DTimeSpace}(n^{O(1)},\lg^{...
- 21.5k
103
votes
15
answers
11k
views
A simple decision problem whose decidability is not known
I am preparing for a talk aimed at undergraduate math majors, and as part of it, I am considering discussing the concept of decidability. I want to give an example of a problem that we do not ...
- 11.9k
102
votes
41
answers
15k
views
What are the recent TCS books whose drafts are available online?
Following the post What Books Should Everyone Read, I noticed that there are recent books whose drafts are available online.
For instance, the Approximation Algorithms entry of the above post cites ...
85
votes
20
answers
11k
views
Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?
Please list examples where a theorem from mathematics which was not normally considered to apply in computer science was first used to prove a result in computer science. The best examples are those ...
79
votes
14
answers
23k
views
Uses of algebraic structures in theoretical computer science
I'm a software practitioner and I'm writing a survey on algebraic structures for personal research and am trying to produce examples of how these structures are used in theoretical computer science (...
- 893
71
votes
17
answers
9k
views
Polynomial-time algorithms with huge exponent/constant
Do you know sensible algorithms that run in polynomial time in (Input length + Output length), but whose asymptotic running time in the same measure has a really huge exponent/constant (at least, ...
65
votes
5
answers
2k
views
Problems that can be used to show polynomial-time hardness results
When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find ...
- 13.5k
58
votes
5
answers
32k
views
What CS blogs should everyone read?
Many top notch computer science researchers and research groups) maintain active blogs that keep us updated on the latest research in the authors' fields of interest. In most cases, blog posts are ...
55
votes
2
answers
4k
views
Can one amplify P=NP beyond P=PH?
In Descriptive Complexity, Immerman has
Corollary 7.23. The following conditions are equivalent:
1. P = NP.
2. Over finite, ordered structures, FO(LFP) = SO.
This can be thought of as "...
- 18.9k
51
votes
8
answers
5k
views
Are there non-constructive algorithm existence proofs?
I remember I might have encountered references to problems that have been proven to be solvable with a particular complexity, but with no known algorithm to actually reach this complexity.
I struggle ...
- 8,911
44
votes
7
answers
6k
views
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 ...
- 3,743
40
votes
7
answers
7k
views
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. ...
- 835