45 votes

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

To complete the other answers: I think that Turing Machine are a better abstraction of what computers do than finite automata. Indeed, the main difference between the two models is that with finite ...
Denis's user avatar
  • 8,843
32 votes
Accepted

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

There are two approaches when considering this question: historical that pertains to how concepts were discovered and technical which explains why certain concepts were adopted and others abandoned or ...
chazisop's user avatar
  • 3,796
32 votes

Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time

There's an algorithm for multiplying an $N \times N^{0.172}$ matrix with an $N^{0.172} \times N$ matrix in $N^2 \operatorname{polylog}\left(N\right)$ arithmetic operations. The main identity used for ...
Josh Alman's user avatar
30 votes
Accepted

Is Descriptive Complexity dead?

I also have the impression that Descriptive Complexity is a less active area of research nowadays. Nevertheless, there are some topics in which people are still active: Rank logics: Rank Logic is ...
Bartosz Bednarczyk's user avatar
27 votes

Theoretical explanations for practical success of SAT solvers?

I am assuming that you are referring to CDCL SAT solvers on benchmark data sets like those used in the SAT Competition. These programs are based on many heuristics and lots of optimization. There were ...
Kaveh's user avatar
  • 21.6k
24 votes

Theoretical explanations for practical success of SAT solvers?

I am typing this quite quickly due to severe time constraints (and didn't even get to responding earlier for the same reason), but I thought I would try to at least chip in with my two cents. I ...
Jakob Nordstrom's user avatar
19 votes

Theoretical explanations for practical success of SAT solvers?

I'm not an expert in this area, but I think the random SAT / phase transition stuff is more or less completely unrelated to the industrial/practical applications stuff. E.g., the very good solvers ...
Ryan O'Donnell's user avatar
18 votes

Theoretical explanations for practical success of SAT solvers?

Let me add my two cents of understanding to this, even though I've never actually worked in the area. You're asking one of two questions, "what are all the known approaches to proving theoretical ...
Magnus Wahlström's user avatar
18 votes

What is the "question" that programming language theory is trying to answer?

The overall purpose of PLT is to make industrial software engineering (in a general sense) cheaper (also in a general sense), through optimising the most important tool (programming languages) and ...
Martin Berger's user avatar
17 votes

Theoretical explanations for practical success of SAT solvers?

There is a paper "Relating Proof Complexity Measures and Practical Hardness of SAT" by Matti Järvisalo, Arie Matsliah, Jakob Nordström, and Stanislav Živný in CP '12 that attempts to link the hardness ...
Jan Johannsen's user avatar
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 CS theories are absolutely paramount for someone new to TCS to understand?

(Disclaimer: this answer has a focus on programming languages theory, which is only one of the many disciplines under the TCS umbrella. Apologies for the length.) A small digression You are asking ...
chi's user avatar
  • 678
15 votes

Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time

Well, one thing is I think that all the constructions we know of - and even the families of potential constructions that people have proposed (e.g., Cohn-Umans approaches, generalizations of ...
Joshua Grochow's user avatar
15 votes

Is Descriptive Complexity dead?

Definitely still active in the area of Weisfeiler-Leman-style algorithms for isomorphism problems such as Graph Isomorphism. The connection with logic was first (I believe) made in Immerman-Lander ...
Joshua Grochow's user avatar
12 votes

Implications of unprovability of $P\neq NP$

As proved in the paper "On The Independence of P Versus NP" by S. Ben-David and S. Halevi: If $P \neq NP$ can be shown to be independent of Peano Arithmetic, then NP has extremely-close-to-...
Avi Tal's user avatar
  • 1,606
10 votes

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

Andrej Bauer gave one important reason in the comments: Because sometimes $\infty$ is a better approximation to $10000000000000000000000000000000$ than $10000000000000000000000000000000$. Let me ...
Thomas Klimpel's user avatar
9 votes

Why exactly are complexity theorists interested in closed timelike curves?

Sorry for the very "big picture" answer from a non-quantum-theorist, but this contrast might help: you could describe algorithms as the study of how to solve computational problems, whereas complexity ...
usul's user avatar
  • 7,615
9 votes
Accepted

Why exactly are complexity theorists interested in closed timelike curves?

I think the big question here is "What does the complexity/power of algorithms look like in our universe?" If we ignore relativity and QM, then plain vanilla Turing machines are a decent model. But ...
Joshua Grochow's user avatar
8 votes

possible bridge between group growth theory and complexity theory?

Maybe this is along the lines you are looking for: I wrote a blog post here explaining how you can use Gromov's theorem on groups of polynomial growth to show that non-uniform read once automata are ...
Izaak Meckler's user avatar
8 votes

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

A formalism is useful or not, based on what people want to use the formalism to model and understand. The Turing machine is a formalism that is useful for understanding programs. Programs are worth ...
Eric Allender's user avatar
8 votes
Accepted

How powerful is $ACC^0$ circuit class in average case?

There seem to be typos in what you wrote; I take it you're asking: is there a function $f \in NEXP$ such that for all polynomials $p$ and infinitely many $n$, no ACC0 circuit of $p(n)$ size can ...
Ryan Williams's user avatar
8 votes
Accepted

Is Biological Computation a theme covered by the Theoretical Computer Science?

Yes there is some overlap, for instance the conference Unconventional Computation and Natural Computation (UCNC) covers theoretical computer science topics related to biological computation. From the ...
Bjørn Kjos-Hanssen's user avatar
8 votes
Accepted

Qubit gates in google supremacy

Based on a fairly cursory inspection of their paper, IBM is clearly aware of the spatial locality. They seem to in fact have taken spatial locality into account when designing their simulation. They ...
Peter Shor 's user avatar
7 votes

Collection of failed attempts to solve X

I've idly entertained the idea of an online arxiv overlay "journal" of negative results. The idea would be to allow negative results or counterexamples that don't seem suitable for a full publication ...
usul's user avatar
  • 7,615
7 votes
Accepted

Implications of faster randomized $CIRCUIT SAT$ algorithm

The gist of the proof of the proposition you're talking about is to simply cite that $EXP\subset P/poly$ implies $EXP=\Sigma_2^p$ (there is a short proof of this in the Arora and Barak book in the ...
Dylan McKay's user avatar
7 votes
Accepted

Consequences of faster parameterized integer programming

An instance of CNF-SAT with $k$ variables can easily be written as a 0/1 integer linear program over the same variable set, since a clause such as $x_1 \vee x_3 \vee \neg x_4 \vee \neg x_6$ naturally ...
Bart Jansen's user avatar
  • 5,265
6 votes

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

Actual computers are not FSAs. An actual computer is a universal computer, in the sense that we can describe a computer for a computer to emulate and the computer will emulate it. For many examples, ...
Eric Towers's user avatar
6 votes

Why is the consensus problem so important in distributed computing?

One reason consensus problems are important is that they are very simple and they are kind of universal problems for distributed computing systems. If we can solve consensus in an async distributed ...
Kaveh's user avatar
  • 21.6k
6 votes

Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)

Some of the work of Olivier Finkel seems related to the question---though not necessarily explicitly about the Axiom of Choice itself---and in line with Timothy Chow's answer. For instance, quoting ...
Sylvain's user avatar
  • 3,374

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