16 votes
Accepted

Provable gaps between decision tree complexity and "true" complexity

Meyer auf der Heide described a non uniform family of linear decision trees for Subset Sum with depth $O(n^4\log n)$. A similar result can be deived from a later algorithm of Meiser for point ...
user avatar
  • 22.8k
11 votes

Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?

It depends on the precise definition of RAM being used, but (for most reasonable definitions of RAMs) this would also imply that SAT is not solvable in $O(n^{2-e})$ time by multitape TMs, a ...
user avatar
8 votes

Where does the modern canonical version of the Turing machine come from?

Is it due to Sipser? Or Penrose? Sorry, that made me laugh out loud. Penrose? Today's notion of formal language (a language is a set of words or strings) can be traced at least as far back as Frege ...
user avatar
7 votes
Accepted

On the complexity of a "list" datastructure in the RAM model

It appears that all of these operations can be performed in time $O(\log n/\log\log n)$ on a RAM, by combining methods for maintaining a dynamic labeling of the list elements by integers of polynomial ...
user avatar
7 votes

Are there protein-based computational models?

Membrane Computing is a model that is based on the possibility or not of movement of molecules through membranes; also on possible reactions of these molecules inside a membrane compartment. While ...
user avatar
6 votes

Most general setting for fine-grained exponential-time complexity classes?

(Just now noticed this question.) There are a lot of questions in the above question. I will try to just address the last few. Might it be the case that a RAM program can solve general CNF-SAT in ...
user avatar
5 votes

Where does the modern canonical version of the Turing machine come from?

Your question (1) is essentially the difference between Turing machines that recognize languages and Turing machines that compute functions. This difference is essential for proving theorems about ...
user avatar
5 votes

Looking for some lecture videos on logic, models of computation and computational complexity/tcs fundamentals

Ryan O'Donnell (professor at Carnegie Mellon) has a wonderful undergraduate complexity theory series that goes through the fundamentals quite well, and he's an engaging lecturer. He also has a similar ...
user avatar
  • 677
4 votes

what is a model of computation, mathematically?

I think that different mathematical models of computation capture different aspects of physical reality. Similar to models of solid state physics (say), these mathematical models may be largely ...
user avatar
4 votes

Where does the modern canonical version of the Turing machine come from?

I view this question as one in the history of Turing machine theory, which indeed has had more changes than are evident from contemporary textbooks. The Turing model of 1936 was remarkably different ...
user avatar
4 votes
Accepted

Examples of quasilinear vs. essentially linear time translatable models

I will start with an overall comparison of essentially linear v quasilinear, and then give a specific example of the requested computational models. As an equivalence relation, quasilinear time (...
user avatar
4 votes

Reversible Turing tarpits?

Does Reversible Bitfuck qualify? It manipulates a tape of 1-bit cells, and its commands are Command Description > Move right < Move left + Toggle current bit [ If current bit is 0, jump to ...
user avatar
  • 580
4 votes

Provable gaps between decision tree complexity and "true" complexity

Here is an example of a trivial gap between decision-tree and algorithmic complexity. The randomized decision tree complexity of local sorting (orienting a vertex-weighted graph) is $O(n\log(\frac{m+...
user avatar
3 votes

Implications of $\mathsf{P}\neq\mathsf{NP}$ in $\mathsf{BSS}$ model

$\newcommand\Ptime{\mathsf P} \newcommand\NP{\mathsf{NP}} \newcommand\poly{\mathsf{poly}}$ It is known that $\Ptime/\poly \neq \NP/\poly \implies \Ptime_{\mathbb C}\neq \NP_\mathbb{C}$ [1] where the ...
user avatar
  • 4,400
3 votes

Most general setting for fine-grained exponential-time complexity classes?

Your description looks correct. The equivalence between deterministic models (under essentially linear time translation) for algorithms using $t^{o(1)}$ space (if the input size is $t^{o(1)}$ or we ...
user avatar
3 votes

what is a model of computation, mathematically?

As others have pointed out, "model of computation" is an open-ended concept that can hardly be captured by a single defintion. A similar example in traditional mathematics is "space". However, this ...
user avatar
  • 26.6k
3 votes
Accepted

Is the following restriction of cellular automata / tile assembly / CRN a known model?

If you partition $\mathbb{Z}^d$ into the $(d-1)$-dimensional slices $S(n) := \{ \vec v | \sum_{k=1}^d \vec v_k = n \}$, then your model is essentially a spacetime diagram of the $(d-1)$-dimensional ...
user avatar
2 votes

Looking for some lecture videos on logic, models of computation and computational complexity/tcs fundamentals

Prof. Tim Roughgarden (Stanford University) Lectures on algorithms and more are also great. He is one of the best lecturers out there... https://www.youtube.com/channel/UCcH4Ga14Y4ELFKrEYM1vXCg/...
user avatar
  • 1,456
2 votes

Running an algorithm for fixed amount of time on RAM model machine

One approach is to implement an interpreter for the RAM model, and then instrument the interpreter with a counter that keeps track of the number of instructions executed. I suspect it should be ...
user avatar
  • 10.4k
2 votes

Are there protein-based computational models?

There are models of how to compute with arbitrary chemical reactions using molecules that drift around and randomly collide. They crop up in parallel computing models sometimes. It's probably not what ...
user avatar
2 votes

Characterisation of P in terms of register machines

The classic reference for these kind of results is the survey by Peter van Emde Boas, "Machine Models and Simulations", the first chapter of Handbook of Theoretical Computer Science, Vol. A. For ...
user avatar
  • 21.3k
2 votes
Accepted

What is the state of the art research in analysing algorithms on GPU architectures?

research into GPU algorithms continues and it is well suited to some problems, but some of the initial excitement may be wearing off after lackluster results and difficulty of translating problems ...
user avatar
  • 10.8k
2 votes

Reversible Turing tarpits?

Many years ago I created a language called Kayak (language spec, esolangs.org entry) that was meant to be a reversible-computing tarpit. It's slightly less primitive than Reversible Brainfuck, since ...
user avatar
  • 176
1 vote
Accepted

Characterisation of P in terms of register machines

I was finally able to find a reference (not necessarily the oldest one) for the efficient simulation of Turing machines by means of RAMs without indirect addressing (nor binary shift): Takumi Kasai,...
user avatar
1 vote

Which model of computation is "the best"?

On a more theoretical note: The article Ultimate theoretical models of nanocomputers argues that the reversible 3D mesh model is the optimal physical model of computation, in the sense that no other ...
user avatar
  • 580

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