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 ...
- 8,598
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 ...
- 3,751
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 ...
- 421
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 ...
- 21.5k
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 ...
- 504
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 ...
- 1,801
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 ...
- 803
17
votes
Status quo of category theory and monads in theoretical computer science research?
There have been a number of developments with regards to the use of monads in the theory of computation since Eugenio Moggi's work. I am not able to give a comprehensive account, but here are some ...
- 28.3k
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 ...
- 4,631
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 ...
- 1,934
17
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 ...
- 11.4k
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 ...
- 668
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 ...
- 36.9k
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-...
- 1,596
11
votes
Uncertainties in GCT program
It depends what you count as "the GCT program."
Consider the specific suggestion (GCT I, GCT II) to use the vanishing/nonvanishing of certain multiplicities in the orbit closures of the determinant ...
- 36.9k
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 ...
- 3,033
10
votes
Accepted
Consequences of $NP\subseteq P/poly$ to $BQP$
I'm not aware of any direct consequence of $NP\subset P/poly$ for $BQP$. Of course it might lessen the interest in quantum computing, since it would mean that we could do something far more ...
- 13.6k
9
votes
Consequences of $NP\subseteq P/poly$ to $BQP$
If $\mathsf{NP} \subseteq \mathsf{P/poly}$, then $\mathsf{PH}$ collapses to $\mathsf{\Sigma_2 P}$ (Karp-Lipton), and in fact to $\mathsf{S_2 P}$ (attributed to Sengupta by Cai, FOCS 2001), and even to ...
- 36.9k
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 ...
- 7,595
8
votes
Uses of algebraic structures in theoretical computer science
Algebra (and algebraic geometry) has had a pretty big role to play in cryptography, with elliptic curve groups, (number-theoretic) lattices, and of course $\mathbb{Z}_p$ being the basis for nearly all ...
- 109
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 ...
- 431
8
votes
Accepted
Implications of a recent negative result to geometric complexity
It means that to separate permanent from determinant (a la GCT) one must either (a) use actual differences in multiplicities (and not merely their vanishing or non-vanishing) in order to get an ...
- 36.9k
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 ...
- 1,761
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 ...
- 27.3k
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 ...
- 4,475
8
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 ...
- 36.9k
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 ...
- 24.3k
7
votes
Accepted
Lower bounds for nonuniform circuits and oracles separating complexity classes
Yes, yes, and yes.
The basic idea is to consider the characteristic function of a language $L$
(the oracle you're constructing) at length $n$ as a string of length $2^n$
that will be an input to a ...
- 36.9k
Only top scored, non community-wiki answers of a minimum length are eligible