China
Africa
Explore chapters and articles related to this topic
Basic Concepts
Published in Michael Pecht, Placement and Routing of Electronic modules, 2020
Guoqing Li, Yeun Tsun Wong, Michael Pecht
If there exists a solution with a polynomial time bound for the satisfiability problem, then all NP problems become P problems because all NP problems can be transformed to the satisfiability problem. The satisfiability problem is also called an NP-complete problem – historically, the first such problem. To prove a problem, P1, to be NP-complete, the following two steps are usually required: Prove problem P1 is an NP problem.Prove that another problem, P2, which is an NP-complete problem, can be transformed to problem P1 in polynomial time.
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.
Cuckoo Search Algorithm, Glowworm Algorithm, WASP, and Fish Swarm Optimization
Published in Anand Nayyar, Dac-Nhuong Le, Nhu Gia Nguyen, Advances in Swarm Intelligence for Optimizing Problems in Computer Science, 2018
Ouaarab, Ahiod, & Yang (2014) proposed an improvised and discrete version of the cuckoo search for the TSP. Ouyang et al. (2013) have proposed a discrete version for the spherical TSP. TSP can be defined as an NP-hard combinatorial optimization problem, where a salesman visits a finite number of cities, such that each city is covered only once, and then finally returns to the initial city. The tour of the salesman should be constructed such that the overall cost and distance travelled are minimized. The authors proved that their discrete version of the CS algorithm can be adapted to other optimization problems by reconstructing the population.
Block SMRT and knapsack optimization-based sequency selector for robust, imperceptible, and payload-efficient color image watermarking for binary watermark
Published in International Journal of Computers and Applications, 2023
Febina Ikbal, Rajamma Gopikakumari
Performance of a watermarking system is highly dependent on parameters and positions used for embedding. Most of the existing watermarking techniques determine their parameters and embedding positions analytically. Watermarking algorithms provide a large parameter space, making it difficult to analytically determine the watermarking parameters, and hence optimization is the solution. Embedding positions and parameters to provide optimized robustness, quality and payload can be achieved through metaheuristic optimization techniques. Travelling Salesman Problem (TSP) is an example of an NP-hard problem where the solution space grows exponentially as the size of the problem increases, rendering an exhaustive search infeasible. Metaheuristic is an iterative approach that intelligently searches for the optimal solution within a search space with all possible solutions. Quality of any solution is defined as a fitness function according to the design objectives. The fitness function in multi-objective optimization problem is evaluated by measuring all objective functions. The solutions chosen per iteration are then ranked according to their measurable objectives using a multi-objective optimization process.
Integrated planning of maintenance operations and workload allocation
Published in International Journal of Production Research, 2023
Melek Rodoplu, Stéphane Dauzère-Pérès, Philippe Vialletelle
The complexity of can be analysed by reducing the problem to a knapsack problem which is NP-complete (see for example Garey and Johnson 1979). This can be done by fixing variables so that all periods are fully used except a single period t and by allowing all maintenance operations to be performed in period t. Then, the problem is equivalent to minimising the total cost of not planning the maintenance operations in a single period (the knapsack), where each maintenance operation o (object to be added in the knapsack) with processing time (size of object in knapsack) has a cost if it is planned in t (or equivalently a profit of if the object is added in the knapsack). Hence, our problem is at least as hard as the knapsack problem.
Beyond geometric complexity: a critical review of complexity theory and how it relates to architecture engineering and construction
Published in Architectural Science Review, 2019
Evangelos Pantazis, David Jason Gerber
In computer science, computational complexity is the amount of computational effort that goes into solving a decision problem starting from a given problem formulation (Traub, Włodzimierz Wasilkowski, and Woźniakowski 1983). Within this classification, non-deterministic polynomial time complexity (NP) is one of the most fundamental complexity classes and is defined as the set of all decision problems for which the instances where the answer is yes have efficiently verifiable proofs of the fact that the answer is indeed ‘yes’ (Barton, Berrywick, and Ristad 1987; Horgan 1995). In other words, computational complexity describes how the time required to solve a problem using a currently known algorithm increases as the size of the problem increases. Depending on that relationship, problems are classified as Polynomial Time (P), Non-Deterministic Polynomial Time (NP), NP-Complete or NP-Hard, which describes whether a problem can be solved and how quickly. For NP-complete problems for instance, although a solution can be verified as correct there is no known way to solve the problem efficiently (Cobham 1965). A famous example of a NP-complete problem is that of a travelling sales person (TSP) which was formulated in the 1800s by W.R. Hamilton and states: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city? (Rosenkrantz, Stearns, and Lewis 1974).