China
Africa
Explore chapters and articles related to this topic
Computational Complexity
Published in Craig A. Tovey, Linear Optimization and Duality, 2020
A problem L1 is NP-complete if L∈NP and every problem L∈NP, can be transformed to L1 in polynomial time, as defined in Section 14.4. The NP-complete problems are the hardest problems in NP in this sense: if you had a fast solution method for an NP-complete problem, you could solve any problem in NP quickly. Question: How?40 A problem L is unary NP-complete if it is NP-complete and all numerical values necessary to specify an instance of L are encoded in unary (base 1) rather than binary. For example, the number 13 would have to be encoded as 1111111111111 rather than 1101.
NP-hard Problems and Languages and complements to algorithmic complexity
Published in J.-P. Barthelemy, G. Cohen, A. Lobstein, Catherine Fritsch-Mignotte, Maurice Mignotte, Algorithmic Complexity and communication problems, 2020
J.-P. Barthelemy, G. Cohen, A. Lobstein
This chapter deals mainly with difficult problems (except if P = NP). An NP-complete decision problem is at least as difficult as any problem which belongs to NP. Similarly, a decision problem D which does not belong to NP , and such that D’ ≤PD for some NP-complete problem D’, will be more difficult than any problem of NP. Furthermore, the concept of reduction can be applied to other kinds of problems. For example, if we know for some graph, how to realize a k-colouration, we are able, a fortiori, to answer YES to the corresponding instance of k-COL. To reach such a state of affairs, we have to extend the definition of polynomial transformation. In order to do that, we use Turing machines with oracle. These new machines lead to the notion of T-reducibility. An oracle represents the calling of a subroutine which answers at once. Thus, if D’ ≤PD, and if some oracle solves D, we shall be able to solve D’ in polynomial time.
Introduction
Published in Joseph Y.-T. Leung, Handbook of SCHEDULING, 2004
Suppose P and Q are both NP-complete problems. Then P∝Q and Q∝P. This is because since Q is in the NP-class and since P is NP-complete, we have Q∝P (all problems in the NP-class are reducible to P ). Similarly, since P is in the NP-class and since Q is NP-complete, we have P∝Q. Thus, any two NPcomplete problems are reducible to each other. By our comments earlier, either all NP-complete problems are solvable in polynomial time, or none of them. Today, thousands of problems have been shown to be NP-complete, and none of them have been shown to be solvable in polynomial time. It is widely conjectured that NP-complete problems cannot be solved in polynomial time, although no proof has been given yet. To show a problem to be NP-complete, one needs to show that all problems in the NP-class are reducible to it. Since there are infinite number of problems in the NP-class, it is not clear how one can prove any problem to be NP-complete. Fortunately, Cook [2] in 1971 gave a proof that the Satisfiability problem (see the definition below) is NP-complete, by giving a generic reduction from Turing machines to Satisfiability. From the Satisfiability problem, we can show other problems to be NP-complete by reducing it to the target problems. Because reducibility is transitive, this is tantamount to showing that all problems in the NP-class are reducible to the target problems. Starting from Satisfiability, Karp [3] in 1972 showed a large number of combinatorial problems to be NP-complete.
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).
Multi-objective quasi oppositional Jaya algorithm to solve multi-objective solid travelling salesman problem with different aspiration level
Published in International Journal of Systems Science: Operations & Logistics, 2023
Aaishwarya Bajaj, Jayesh Dhodiya
The travelling salesman problem (TSP) is the most intensive problem in optimization. TSP has a wide range of applications such as in airline crew scheduling and courier delivery services. In courier services, minimizing time is important because it directly impacts the service and reputation of the companies. Reaching these goals requires a system capable of providing an optimal travel route so that the travel time is minimum. So it needs an application that can optimize the TSP solution. TSP was mathematically formulated in 1930 but became popular after the 1950s. TSP entails travelling to each city from the given list exactly once using the shortest possible route and return to the origin city. It is an NP-hard combinatorial optimization problem described by Liao et al. (2012). The decision version of TSP is an NP-Complete problem. NP-complete means no polynomial algorithm can obtain the best solution, i.e. it can not be reduced to any other polynomial-time problem. Hence, heuristic methods are used to solve this type of problem in a reasonable amount of time as discussed by Feng and Liao (2014). TSP is available in different types such as asymmetric TSP in which the travelling cost from node to is not equal for to . On the other hand, symmetric TSP is when travelling cost from node to is equal to the cost from to . Changdar et al. (2014) describe stochastic TSP which uses probability for the visited vertex to minimise the travelling cost. In time window TSP, every vertex is visited within the indicated window time. In double TSP, two salesmen are appointed to complete the tour, operating simultaneously. These different types of TSP were explored and solved by researchers during the last two decades.
A twofold update quantum-inspired genetic algorithm for efficient combinatorial optimal decisions in engineering system design and operations
Published in Journal of Engineering Design, 2023
Pan Zou, Jianxin (Roger) Jiao, Feng Zhou
Combinatorial optimisation is the process of searching for optima (i.e. maxima or minima) of an objective function whose domain is a discrete but large configuration space with a finite set of possible solutions. The set of possible solutions is generally defined by a set of restrictions that have to be met for items to be selected into groups, and the configuration space is usually too large for exhaustive search. A considerable number of combinatorial optimisation problems, such as the knapsack problem and the Boolean satisfactory problem, are known as NP complete or NP hard. To find the optimal or sufficiently good solutions in practical time, many algorithms have been proposed. In some cases, the problems can be solved exactly using techniques, such as linear programming, dynamic programming, branch-and-bound algorithms (Wolsey and Nemhauser 1999). These algorithms guarantee that an optimal result to be found if one exists. With the appropriate problem formulation modelling and application of many powerful programs, most of non-large-scale problems can be solved within minutes or even seconds. While in other cases, no exact algorithms are feasible and thus, approximation algorithms must be employed with no guarantee to find an optimal solution. Polynomial-time approximation algorithms are often desirable due to their guarantees in the computation efficiency, though many real-life problems are inapproximable. Various heuristics for solving combinatorial optimisation problems have been proposed by many researchers, since the heuristics methods are often easy to implement and can be tailor-made for particular domain problems. Evolutionary Algorithms (EAs) are heuristic-based algorithms inspired by the principles of natural selection, molecular genetics and biological processes; they provide a general approach to solve complex problems, especially for those that cannot be solved in polynomial time easily, as supplements to conventional optimisation methods. Many evolutionary algorithms have been proposed and researched, including Genetic Algorithm (GA), Swarm Algorithms and so on. While the essential feature differences among them are mainly the representation/encoding of chromosomes/individuals, the selection/reproduction strategies, mutation and/or recombination operators (Back 1996), the core mechanism of EAs computation success is associated with a generic population-based metaheuristic and strategies to handle the exploration-exploitation tradeoff (Črepinšek, Liu, and Mernik 2013) even among the most recent variants of EAs (Salgotra et al. 2021; Faramarzi et al. 2020).