China
Africa
Explore chapters and articles related to this topic
Fault tolerance and ultimate physical limits of nanocomputation
Published in David Crawley, Konstantin Nikolić, Michael Forshaw, 3D Nanoelectronic Computer Architecture and Implementation, 2020
A S Sadek, K Nikolić, M Forshaw
If a computation can be solved in polynomial time, then it is classified as belonging to the complexity class P. This complexity class is thought to be a subset of a larger class of decisional problems NP, where the solution requires additional information in the form of a certificate (factoring is an example of such a problem). P and NP are classes of deterministic algorithms, which means they perform the same set of operations every time they are executed on the same input. Once noise becomes a factor (i.e. ϵ > 0), such algorithms are no longer deterministic but random. Such random algorithms, implemented by design or as a result of noise, are part of the greater complexity class BPP (bounded-probabilistic polynomial time). The noise-tolerant architectures that we will explore for nanocomputation will necessarily belong to this complexity class. A corresponding class exists encompassing fault tolerant quantum computation called BQP.
Parallel Algorithms
Published in Vivek Kale, Parallel Computing Architectures and APIs, 2019
In computational complexity theory, problems are divided into several complexity classes according to their running times on a single processor system or a deterministic Turing machine. Tractable problems: Problems whose running times are upper bounded by polynomials in n are said to belong to the P class and are generally considered to be tractable. Even if the polynomial is of a high degree such that a large problem requires years of computation on the fastest available supercomputer, there is still hope that with improvements in the algorithm or in computer performance, a reasonable running time may be obtained.Intractable problems: Problems for which the best-known deterministic algorithm runs in exponential time are intractable. A problem of this kind for which, when given a solution, the correctness of the solution can be verified in polynomial time, is said to belong to the non-deterministic polynomial (NP) class.
Reflections on probabilistic compared to quantum computational devices
Published in International Journal of Parallel, Emergent and Distributed Systems, 2021
Indeed if we reason in a probabilistic way, the constant functions among 2n possible functions on variables are only two, so, as n increases, we probabilistically do an error trending to 0, guessing f is not constant. If we make calculation of t random distinct values on f, and there is among them almost one value different from others, we can affirm with error 0 that f is not constant. In a similar way in [5], we can affirm that after t distinct evaluations of a function f of n variables, the probability that we have not distinguished correctly if f is balanced or constant is So in this case we can have a PTM that simulates efficiently Deutsch–Jozsa quantum algorithm if we admit a probabilistic behaviour and relative error . Of course, we demonstrate that this algorithm belongs to BPP complexity class (Polynomial time if run on PTM), but do not demonstrate that it is already in P (Polynomial time if run on DTM).
Coding-theorem like behaviour and emergence of the universal distribution from resource-bounded algorithmic probability
Published in International Journal of Parallel, Emergent and Distributed Systems, 2019
Hector Zenil, Liliana Badillo, Santiago Hernández-Orozco, Francisco Hernández-Quiroz
Now, let be a class of grammars over a terminal vocabulary T. By we denote the grammars in with complexity c. We then enumerate by increasing the complexity c. To every complexity class corresponds a set of structure classes which is determined by n and p. Therefore a complexity class is enumerated by enumerating each of its structure classes (i.e. every structure S that constitutes ). In addition, we need to define an ordered sequence R which consists of all possible right-hand sides for the production rules. The sequence R is ordered lexicographically (first terminals, then non- terminals) and is defined according to the class of grammars we want to enumerate. For example, suppose we are interested in enumerating the class of Chomsky Normal Form grammars over the terminal vocabulary and the non-terminal vocabulary , we then set .
A generic optimization framework for resilient systems
Published in Optimization Methods and Software, 2023
Marc E. Pfetsch, Andreas Schmitt
The multi-level form of Problem (3) indicates that it is necessary to consider higher levels of the polynomial time hierarchy than the complexity class NP to characterize its computational complexity. For an introduction of the hierarchy we refer to Arora and Barak [7] or Papadimitriou [51]. The complexity class is found on the third level of the hierarchy. It can be defined to be the collection of decision problems which can be written as a logical formula for a Boolean predicate P, which can be evaluated in polynomial time of the size of the Boolean variables .