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
Informally, a decision problem is a computational problem for which the answer is either “yes” or “no”. An example of a decision problem is: Given a graph G, does it have a proper r-coloring? A counting problem is a computational problem for which the answer is the number of satisfying configurations. An example of a counting problem is: given a graph G, how many proper r-colorings does it have? We denote by P, respectively FP, the set of decision problems and counting problems which can be solved in time polynomial in the size of the input. Problems which belong to P or to FP are called tractable, and are considered to be efficiently computable.
Problems and Languages
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
In decision problems there is a statement and a question which requires a YES or NO answer. In this chapter, we shall look at this kind of problem, first from an intuitive point of view, then from a formal one. We shall establish links between problems and languages, and we shall also introduce the notion of reduction of languages and problems (how can one problem be changed into another?). A final paragraph will give an intuitive presentation of questions treated in the next chapter. The problems given at the beginning of this chapter are more than games. The proofs of complexity, which we shall give later, will depend on them.
Mathematical Background
Published in Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography, 2018
Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone
For simplicity, the theory of computational complexity restricts its attention to decision problems, i.e., problems which have either YES or NO as an answer. This is not too restrictive in practice, as all the computational problems that will be encountered here can be phrased as decision problems in such a way that an efficient algorithm for the decision problem yields an efficient algorithm for the computational problem, and vice versa.
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).
Optimal allocation of public parking spots in a smart city: problem characterisation and first algorithms
Published in Journal of Experimental & Theoretical Artificial Intelligence, 2019
Javier Arellano-Verdejo, Federico Alonso-Pecina, Enrique Alba, Adolfo Guzmán Arenas
● constructing a polynomial time reduction from to . Theorem 1. The optimal allocation of public parking spots is NP-complete.Proof: A decision problem is a question in a formal system with a yes-or-no answer, depending on the values of some input parameters, and this is NP if the instances where the answer is ‘yes’ have efficiently verifiable proofs. More precisely, these proofs have to be verifiable by deterministic computations that can be performed in polynomial time. For the problem presented in this paper, the solution can be verified using the method shown in Equation (12). The temporal complexity of Equation (12) grows linearly with respect to the size of the permutation that is , so it is clear that the problem is NP.