Skip to main content
Share Your Experience: Take the 2024 Developer Survey
31 votes
Accepted

Where to learn more about what Theoretical Computer Science is?

First, "theoretical computer science" means different things to different people. I think for most users on this site, a historical caricature (which reflects some modern sociological tendencies) is ...
Joshua Grochow's user avatar
30 votes
Accepted

Is there any book on the philosophical implications of Theoretical Computer Science?

Try the 50+ page essay "Why Philosophers Should Care About Computational Complexity" https://arxiv.org/abs/1108.1791
Ryan Williams's user avatar
23 votes
Accepted

Sources of open problems?

Here's a partial list of collections of open problems in TCS, broadly construed. Note that a collection of "major open problems" exists already on this site: http://cstheory.stackexchange.com/...
Huck Bennett's user avatar
  • 4,878
21 votes
Accepted

Entropy and computational complexity

Yes, but most of the work so far (except very recently, see below) has focused on turning irreversible computations into reversible ones, thereby hoping to avoid any entropy generation. (Note: there ...
Joshua Grochow's user avatar
20 votes

Is there a relationship between relational algebra/calculus and category theory?

Categorical approaches to query languages is a bit of a niche interest, but I think it's a very interesting niche! Two of the key figures in this area are Peter Buneman and Torsten Grust. Obviously, ...
Neel Krishnaswami's user avatar
20 votes
Accepted

Is there a counterexample to this work?

Predecessor versions of this paper have been around for more than 15 years. I remember that there were counter-examples to the first versions, then first revisions, counter-examples to the first ...
Gamow's user avatar
  • 5,772
17 votes

Easy problems with hard counting versions

One interesting example from number theory is expressing a positive integer as a sum of four squares. This can be done relatively easily in random polynomial time (see my 1986 article with Rabin at ...
Jeffrey Shallit's user avatar
17 votes

Easy problems with hard counting versions

A very nice and simple example from Graph Theory is counting the number of Eularian circuits in an undirected graph. The decision version is easy (... and the Seven Bridges of Königsberg problem has ...
Marzio De Biasi's user avatar
17 votes
Accepted

Is the Kolmogorov complexity of the truth tables of the halting problem known asymptotically?

Hmm, turns out there's actually an matching upper bound that isn't too hard: To produce the truth table $HALT_n$ in a finite amount of time, the only information that is needed is the number of ...
Chris Beck's user avatar
17 votes
Accepted

Parameterized complexity of inclusion of regular languages

The particular case of language universality (are all words accepted ?) is PSPACE-complete for regular expressions or NFAs. It answers your question: in general the problem stays PSPACE-complete even ...
Denis's user avatar
  • 8,893
17 votes

Possible to do Complexity theory with only counting and Pigeonhole

If you are looking for non-pigeon-hole type arguments, then there is good news: they exist! The pigeon-hole principle is a certain template for proof by contradiction. There are concepts in TCS which ...
Lieuwe Vinkhuijzen's user avatar
16 votes
Accepted

What is the name of a function $f$ such that $f(x,y) \in L \iff x\in L \wedge y \in L$?

They are typically called AND-functions. (I'm not joking.) Indeed, this concept has been considered before, and that's what people call them. See, for example, the book by Kobler, Schoning, and Toran ...
Joshua Grochow's user avatar
16 votes

Is there any book on the philosophical implications of Theoretical Computer Science?

Quantum Computing Since Democritus by Scott Aaronson is the closest match I can think of. I don't think there is a single book completely devoted to philosophical implications of TCS.
Gustav Nordh's user avatar
  • 1,047
16 votes
Accepted

On theoretical aproaches for solving $\mathsf{SAT}$ in special cases

Concerning Question 1, there have mainly been two lines of work to find tractable restrictions of SAT. The first one that you are already familiar with is to restrict the types of the clauses that ...
holf's user avatar
  • 2,174
16 votes
Accepted

NP-hard problems with very fast exponential-time algorithms

The desired property holds for Independent Set (and probably other problems) in graphs of suitably bounded tree width. Fix any constant $\epsilon>0$ and consider the Independent Set problem ...
Neal Young's user avatar
  • 10.8k
15 votes
Accepted

Novel proof of pumping lemma for regular languages

Essentially the same argument is made by Andries P.J. van der Walt (1976, Lemma 2.3 and Example 2.9) for the variant of the pumping lemma where $N$ letters are marked and all three of $x$, $y$, $z$ ...
Sylvain's user avatar
  • 3,374
15 votes
Accepted

Connectivity of a random regular graph of degree $d$

For constant $d \geq 3$, a random $d$-regular graph is connected with high probability. In fact, it is an expander with high probability. See for example this note by David Ellis. Friedman even showed ...
Yuval Filmus's user avatar
  • 14.5k
15 votes

Languages that we cannot (dis)prove to be Context-Free

Another good one is the complement of the set $S$ of contiguous subwords (aka "factors") of the Thue-Morse sequence ${\bf t} = 0110100110010110 \cdots $. To give some context, Jean Berstel proved ...
Jeffrey Shallit's user avatar
15 votes
Accepted

Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?

This CSP is known to be SETH-hard. More precisely, assuming SETH, for any constant $\varepsilon > 0$ there is no $d^{(1-\varepsilon)n}$-time algorithm for solving this CSP with domain size $d$. ...
Huck Bennett's user avatar
  • 4,878
14 votes
Accepted

Rabin's "degree of difficulty of computing a function, and a partial ordering of recursive sets"

There are two loanable copies at The National Library of Israel. Here is a scanned copy.
Yuval Filmus's user avatar
  • 14.5k
14 votes
Accepted

Structural Complexity Theory References

I don't think there really are canonical references for this stuff (roughly: advanced modern structural complexity theory), but here are some references. This list is partially geared towards my ...
Joshua Grochow's user avatar
14 votes
Accepted

Complexity of NFA cofiniteness

Lemma 1. Determining whether a given NFA is cofinite is PSPACE-hard. Proof. The proof is by an easy reduction from the PSPACE-complete problem of determining whether a given NFA is universal. The ...
Neal Young's user avatar
  • 10.8k
13 votes
Accepted

Is intersection of $k \ge 3$ graphic matroids in P?

I think it is still NP-complete, by a reduction from Hamiltonian paths in bipartite graphs with two degree-one vertices and all other vertices having degree three. (This is just the same as finding ...
David Eppstein's user avatar
13 votes

Languages that we cannot (dis)prove to be Context-Free

How about the language $L_{TP}$ of twin primes? I.e., all pairs of natural numbers $(p,p')$ (represented, say, in unary), such that $p,p'$ are both prime and $p'=p+2$? If twin primes conjecture is ...
Aryeh's user avatar
  • 10.6k
13 votes
Accepted

Best parameterized algorithm for maximum clique

Maximum clique in graphs with degree $d$ can be reduced to $n$ instances of maximum clique in a graph with at most $d$ vertices: for each vertex, compute maximum clique in the induced subgraph of the ...
Laakeri's user avatar
  • 1,786
13 votes
Accepted

Is there a language of first-order logic such that every r.e. set is Turing-equivalent to some finitely axiomatizable theory in that language?

The answer is yes. This was proved by Hanf (Model-theoretic methods in the study of elementary logic, in the Theory of models volume). A "uniform" version of this result was conjectured by ...
Noah Schweber's user avatar
12 votes
Accepted

Primary source for the equivalence of non-deterministic polynomial time and deterministic polynomial time verification

[An extended comment] I think that the "roots of verification" are already contained in Karp's milestone paper "Reducibility Among Combinatorial Problems" (1972): ... Let $P^{(2)}$ denote the ...
Marzio De Biasi's user avatar
12 votes
Accepted

Is there a useful notion of being “approximately computable”

If the family function $f(x,n)=f_n(x)$ is computable then these are exactly the $\Delta^0_2$ functions, or equivalently, the functions that are Turing reducible to the halting set $0'$, which are very ...
Bjørn Kjos-Hanssen's user avatar
12 votes
Accepted

Number of simple paths between two vertices in a DAG

Every simple path is uniquely determined by the subset of vertices that it passes through: if you topologically order the DAG (arbitrarily) then a path through any subset of vertices must go through ...
David Eppstein's user avatar
11 votes

$RL=L$ Progress Since 2006

One line of work has shown how to improve the analysis of the classic INW PRG for the special cases of fooling regular and permutation branching programs. The seed length is only $\widetilde{O}(\log n)...
William Hoza's user avatar
  • 1,743

Only top scored, non community-wiki answers of a minimum length are eligible