All Questions

1,665 questions
Filter by
Sorted by
Tagged with
26k 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? ...
147k views

[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 ...
184k views

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 ...
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,536
99k 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: ...
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 ...
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
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,956
6k 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$) ...
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,812
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,336
48k 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 ...
22k 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,806
12k 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
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
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 ...
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'...
6k 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.7k
5k 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-...
• 19.1k
11k 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 ...
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 ...
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,478
11k 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.5k
26k 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 ...
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,687
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$, ...
• 431
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?
• 7,020
132k 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,981
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 ...
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 ...
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 ...
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

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,668
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.7k
10k 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
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.3k
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
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
713 views

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.7k 104 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 ... • 12k 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 ... 81 votes 14 answers 24k 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 (... • 913 71 votes 17 answers 10k 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.7k 59 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 ... 56 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 "... • 19.1k 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,981 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,763 40 votes 3 answers 4k views 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 ...
• 403

15 30 50 per page