China
Africa
Explore chapters and articles related to this topic
The exact complexity of the Tutte polynomial
Published in Joanna A. Ellis-Monaghan, Iain Moffatt, Handbook of the Tutte Polynomial and Related Topics, 2022
Tomer Kotek, Johann A. Makowsky
So far the complexity of computational problems was measured with respect to one parameter of the input only: the size of the input (e.g., the number of vertices or edges of the input graph). Parameterized complexity measures the complexity of problems in terms of additional parameters of the graph. A problem is fixed-parameter tractable with respect to a parameter k if there is a computable function f, a polynomial p, and an algorithm solving the problem in time f(k)·p(n), where n is the size of the problem, and the function f(k) only depends on k. However, f may grow arbitrarily in k, and indeed is often exponential in k. The set of fixed-parameter tractable decision problems is denoted by FPT.
Modelling distributive computation by selective machines
Published in International Journal of Parallel, Emergent and Distributed Systems, 2021
In 2007, it was demonstrated and proved mathematically in what conditions interactive computation is more powerful than computation of Turing machines and in what conditions interactive computation has the same computing power [7,8]. Five sources for higher power of interaction were found. Namely, recursive algorithms, such as Turing machines, become super-recursive, i.e. have higher computing power, when: (1) the interactive algorithm is itself super-recursive; (2) the interactive algorithm is recursive but contains initial information about some recursively non-computable function (has a non-recursive oracle); (3) the interactive recursive algorithm interacts with a super-recursive algorithm (a non-recursive environment); (4) time of interaction is not recursively coordinated; (5) communication space is not recursively coordinated. The first three cases are evident because either super-recursive power comes not from interaction (case 1) or as it is well known, if a recursive device has access to super-recursive information, then this device can compute recursively non-computable functions (cases 2 and 3). For instance, Turing machines with oracles have such a super-recursive power because oracles can supply any information to the Turing machine.