# Tag Info

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 ...
• 22.8k

### 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 ...
• 26.3k

### 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 ...
• 6,888
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 ...
• 50.2k

### 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 ...

### 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 ...
• 26.3k

### 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 ...
• 23.5k

### 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 ...
• 677

### 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 ...
• 5,424

### 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 ...
• 141
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 (...
• 2,237

### 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 ...
• 580

• 661

### 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/...
• 1,456

### 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 ...
• 10.4k

### 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 ...

### 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 ...
• 21.3k
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 ...
• 10.8k

### 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 ...
• 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,...
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 ...
• 580

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