# Tag Info

16

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 location in hyperplane arrangements. Of course the problem is NP-hard.

11

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 longstanding open problem. The reason is that there is a very efficient reduction from linear time on RAMs to SAT (in general, nondeterministic quasi linear time on RAMs ...

8

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 in the late 1800's and Thue in the early 1900's. Chomsky's 1956 paper was very influential, and definitely uses the term "language" for a set of strings. ...

7

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 this is not specifically talking about proteins, in reality some of these molecules and the channels through which they pass would be proteins. Here is an ...

7

I essentially agree with Martin's comment, I can elaborate on that to make a tentative answer, knowing that there is no general formal definition of calculus or abstract machine and that what I am going to describe cannot possibly cover the meaning of all instances of these two words found in the literature. In brief: a calculus usually gives you the ...

7

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 magnitude (e.g. Bender et al, "Two Simplified Algorithms for Maintaining Order in a List", ESA 2002, https://erikdemaine.org/papers/DietzSleator_ESA2002/) with ...

6

(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 exponential time with a base less than 2, but also requiring exponential space, so that when translated to a TM the algorithm runs in exponential time with a base ...

5

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 complexity classes like NP. And in fact, if we look at Cook's 1971 paper The Complexity of Theorem-Proving Procedures, which proved the Cook-Levin theorem, we find ...

4

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 graduate lecture series that mostly picks up where the undergrad series left off. (Note that this series does not cover logic, and I'm not aware of any videos ...

4

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 incomparable. Think of analog computers, where the model may not even be described with discrete math. When it comes to automata and formal languages (of finite words ...

4

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 (denoted using $\tilde{O}$) is the most fine-grained measure that is robust between a number of different sequential deterministic models. By contrast, essentially ...

4

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+n}{n}))$ whereas the size of the input is $\Theta(n+m)$. Any algorithm needs to read the input, so there's a separation whenever $m=\omega(n)$. See Goddard, ...

4

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 from the later more accepted formulations. In more detail in terms of your questions: (1),(2) The modern formulation in terms of Recogniser, and Languages ...

3


2

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 you're looking for, but it might be interesting to learn about. For an example, the ambient calculus. The process calculus wikipedia page includes some others.

2

Consider the following lazy functional program: doArith :: Int -> Int doArith n = if n < 0 then 1 + 2 else 3 - 4 A compiler can figure out that it doesn't need to build a thunk for 1 + 2 or 3 - 4 in the if expression. This is because that an if expression is strict in the branch position, since either 1 + 2 or 3 - 4 will surely be evaluated after ...

2

Short answer: yes. Long answer: Using process algebra as a witness to the claimed existential is certainly admissible, but the way the question is phrased might warrant are more direct answer. If TMs are used as mathematical model for sequential computation, we can surely come up with a concurrent version, and show that it is no more powerful than the good ...

2

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 simulations between RAM and Turing machines see Theorems 2.5 and 2.6, pp. 26--27. It also contains pointers to historic references.

2

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 into GPU approaches. also in recent times there is some consternation over transfer overhead to/ from the GPU. from anecdotal/ background stories/ conversations ...

1

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, Computational complexity of multitape Turing machines and random access machines, Publications of the Research Institute for Mathematical Sciences 13, 469–496,...

1

I would add that, typically, one uses the term "calculus" when the evaluation rules are expressed at the level of the source language. One use the term "abstract machine" when addition "machine-level" concepts are used in describing the evaluation (such as stores, pointers, stacks, etc.).

1

Also Petri nets form a computational model tailored for concurrency. The basic vanilla system is a finite state based model, but there exist more involved models (having "inhibitor arcs" or "coloured nets") that reach Turing power. Nice part of Petri nets is their graphical nature. Modern application includes the modelling of biological processes (e.g. in ...

1

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 physical model could be asymptotically faster. Physical considerations like the speed of light, Landauer's principle, and the Bekenstein bound are discussed. To ...

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