# All Questions

1,356 questions
18k 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? ...
107k 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 ...
6k 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 ...
156k 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 ...
84k 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: ...
13k 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 ...
3k 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$) ...
6k 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 ...
14k 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 ...
3k 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 ...
3k 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 ...
6k 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 ...
108k views

### Algorithms from the Book.

Paul Erdos 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 Book. If ...
6k 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 ...
8k 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). ...
3k views

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-...
3k views

### What are the best current lower bounds on 3SAT?

What are the best current lower bounds for time and circuit depth for 3SAT?
2k 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 ...
17k 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 ...
6k 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'...
5k 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 ...
5k 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?
4k 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 ...
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$, ...
6k 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. ...
37k 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 ...
15k 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 ...
18k 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 (...
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 ...
2k 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 ...
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 ...
113k 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 ...
13k 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 ...
28k 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 ...
7k 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 ...
7k 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 ...
7k 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 ...
9k views

### A simple 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 ...
7k 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 ...
3k 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 ...
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 ...
7k 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, ...
2k views

### Surprising Results in Complexity (Not on the Complexity Blog List)

What were the most surprising results in complexity? I think it would be useful to have a list of unexpected/surprising results. This includes both results that were surprising and came out of ...
3k views

### Are there any counterintuitive results in theoretical computer science?

Some math and logic paradoxes could be automatically applied to computers probably, but are there any paradoxes that were discovered in computer science itself? By paradoxes I mean counter intuitive ...
4k 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 ...
3k 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 "...
2k views

### NTIME(n^k) ≠ DTIME(n^k) ?

In "On determinism versus nondeterminism and related problems" (Proc. IEEE FOCS, pages 429–438, 1983), Paul, Pippenger, Szemerédi and Trotter proved that $\mathsf{NTIME}(n)\neq\mathsf{DTIME}(n)$. ...
3k 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 ...
Let $0\le p\le 1$ and consider the decision problem CLIQUE$_p$ Input: integer $s$, graph $G$ with $t$ vertices and $\lceil p\binom{t}{2} \rceil$ edges Question: does $G$ contain a clique on at ...