**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# NP (complexity)

Summary

In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine.
NP is the set of decision problems solvable in polynomial time by a nondeterministic Turing machine.
NP is the set of decision problems verifiable in polynomial time by a deterministic Turing machine.
The first definition is the basis for the abbreviation NP; "nondeterministic, polynomial time". These two definitions are equivalent because the algorithm based on the Turing machine consists of two phases, the first of which consists of a guess about the solution, which is generated in a nondeterministic way, while the second phase consists of a deterministic algorithm that verifies whether the guess is a solution to the problem.
It is easy to see that the complexity class P (all problems solvable, deterministically, in polynomial time) is contained in NP (problems where solutions can be verified in polynomial time), because if a problem is solvable in polynomial time, then a solution is also verifiable in polynomial time by simply solving the problem. But NP contains many more problems, the hardest of which are called NP-complete problems. An algorithm solving such a problem in polynomial time is also able to solve any other NP problem in polynomial time. The most important P versus NP (“P = NP?”) problem, asks whether polynomial-time algorithms exist for solving NP-complete, and by corollary, all NP problems. It is widely believed that this is not the case.
The complexity class NP is related to the complexity class co-NP, for which the answer "no" can be verified in polynomial time. Whether or not is another outstanding question in complexity theory.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (6)

Related people (2)

Related units (1)

Related courses (67)

Related concepts (58)

Related MOOCs (2)

CS-455: Topics in theoretical computer science

The students gain an in-depth knowledge of several current and emerging areas of theoretical computer science. The course familiarizes them with advanced techniques, and develops an understanding of f

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

PHYS-641: Quantum Computing

After introducing the foundations of classical and quantum information theory, and quantum measurement, the course will address the theory and practice of digital quantum computing, covering fundament

Related lectures (513)

Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

NP (complexity)

In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine. NP is the set of decision problems solvable in polynomial time by a nondeterministic Turing machine.

Decision problem

In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whether a given natural number is prime. Another is the problem "given two numbers x and y, does x evenly divide y?". The answer is either 'yes' or 'no' depending upon the values of x and y. A method for solving a decision problem, given in the form of an algorithm, is called a decision procedure for that problem.

Information, Calcul, Communication: Introduction à la pensée informatique

Dans une première partie, nous étudierons d’abord comment résoudre de manière très concrète un problème au moyen d’un algorithme, ce qui nous amènera dans un second temps à une des grandes questions d

Information, Calcul, Communication: Introduction à la pensée informatique

Dans une première partie, nous étudierons d’abord comment résoudre de manière très concrète un problème au moyen d’un algorithme, ce qui nous amènera dans un second temps à une des grandes questions d

Quantum Computation Delegation

Covers the concept of quantum computation delegation and the relationship between MIP and RE, addressing common FAQs and discussing helpful materials and interactions with quantum devices.

Effective Field Theory: Testing Weak Interactions

Explores effective field theory for testing weak interactions and parity violation through forward-backward asymmetry.

MHD Equilibrium & StabilityPHYS-325: Introduction to plasma physics

Explores Magnetohydrodynamic equilibrium and stability, ideal MHD solutions, 'hairy ball' theorem, and boundary conditions.

Pascal Frossard, Laura Toni, Xue Zhang, Yao Zhao

Multiview applications endow final users with the possibility to freely navigate within 3D scenes with minimum-delay. A real feeling of scene navigation is enabled by transmitting multiple high-quality camera views, which can be used to synthesize additional virtual views to offer a smooth navigation. However, when network resources are limited, not all camera views can be sent at high quality. It is therefore important, yet challenging, to find the right tradeoff between coding artifacts ( reducing the quality of camera views) and virtual synthesis artifacts ( reducing the number of camera views sent to users). To this aim, we propose an optimal transmission strategy for interactive multiview HTTP adaptive streaming. We propose a problem formulation to select the optimal set of camera views that the client requests for downloading, such that the navigation quality experienced by the user is optimized while the bandwidth constraints are satisfied. We show that our optimization problem is NP-hard, and we therefore develop an optimal solution based on the dynamic programming algorithm with polynomial time complexity. To further simplify the deployment, we present a suboptimal greedy algorithm with effective performance and lower complexity. The proposed controller is evaluated in theoretical and realistic settings characterized by realistic network statistics estimation, buffer management, and server-side representation optimization. Simulation results show significant improvement in terms of navigation quality compared with alternative baseline multiview adaptation logic solutions.

2019The graph coloring problem is one of the most famous problems in graph theory and has a large range of applications. It consists in coloring the vertices of an undirected graph with a given number of colors such that two adjacent vertices get different colors. This thesis deals with some variations of this basic coloring problem which are related to scheduling and discrete tomography. These problems may also be considered as partitioning problems. In Chapter 1 basic definitions of computational complexity and graph theory are presented. An introduction to graph coloring and discrete tomography is given. In the next chapter we discuss two coloring problems in mixed graphs (i.e., graphs having edges and arcs) arising from scheduling. In the first one (strong mixed graph coloring problem) we have to cope with disjunctive constraints (some pairs of jobs cannot be processed simultaneously) as well as with precedence constraints (some pairs of jobs must be executed in a given order). It is known that this problem is NP-complete in mixed bipartite graphs. In this thesis we strengthen this result by proving that for k = 3 colors the strong mixed graph coloring problem is NP-complete even if the mixed graph is planar bipartite with maximum degree 4 and each vertex incident to at least one arc has maximum degree 2 or if the mixed graph is bipartite and has maximum degree 3. Furthermore we show that the problem is polynomially solvable in partial p-trees, for fixed p, as well as in general graphs with k = 2 colors. We also give upper bounds on the strong mixed chromatic number or even its exact value for some classes of graphs. In the second problem (weak mixed graph coloring problem), we allow jobs linked by precedence constraints to be executed at the same time. We show that for k = 3 colors this problem is NP-complete in mixed planar bipartite graphs of maximum degree 4 as well as in mixed bipartite graphs of maximum degree 3. Again, for partial p-trees, p fixed, and for general graphs with k = 2 colors, we prove that the weak mixed graph coloring problem is polynomially solvable. We consider in Chapter 3 the problem of characterizing in an undirected graph G = (V, E) a minimum set R of edges for which maximum matchings M can be found with specific values of p = |M ∩ R|. We obtain partial results for some classes of graphs and show in particular that for odd cacti with triangles only and for forests one can determine in polynomial time whether there exists a minimum set R for which there are maximum matchings M such that p= |R ∩ M|, for p= 0,1, ..., ν(G). The remaining chapters deal with some coloring (or partitioning) problems related to the basic image reconstruction problem in discrete tomography. In Chapter 4 we consider a generalization of the vertex coloring problem associated with the basic image reconstruction problem. We are given an undirected graph and a family of chains covering its vertices. For each chain the number of occurrences of each color is given. We then want to find a coloring respecting these occurrences. We are interested in both, arbitrary and proper colorings and give complexity results. In particular we show that for arbitrary colorings the problem is NP-complete with two colors even if the graph is a tree of maximum degree 3. We also consider the edge coloring version of both problems. Again we present some complexity results. We consider in Chapter 5 some generalized neighborhoods instead of chains. For each vertex x we are given the number of occurrences of each color in its open neighborhood Nd(x) (resp. closed neighborhood Nd+(x)), representing the set of vertices which are at distance d from x (resp. at distance at most d from x). We are interested in arbitrary colorings as well as proper colorings. We present some complexity results and we show in particular that for d = 1 the problems are polynomially solvable in trees using a dynamic programming approach. For the open neighborhood and d = 2 we obtain a polynomial time algorithm for quatrees (i.e. trees where all internal vertices have degree at least 4). We also examine the bounded version of these problems, i.e., instead of the exact number of occurrences of each color we are given upper bounds on these occurrences. In particular we show that the problem for proper colorings is NP-complete in bipartite graphs of maximum degree 3 with four colors and each color appearing at most once in the neighborhood N(x) of each vertex x. This result implies that the L(1,1)-labelling problem is NP-complete in this class of graphs for four colors. Finally in Chapter 6 we consider the edge partitioning version of the basic image reconstruction problem, i.e., we have to partition the edge set of a complete bipartite graph into k subsets such that for each vertex there must be a given number of edges of each set of the partition incident to this vertex. For k = 3 the complexity status is still open. Here we present a new solvable case for k = 3. Then we examine some variations where the union of two subsets E1, E2 has to satisfy some additional constraints as for example it must form a tree or a collection of disjoint chains. In both cases we give necessary and sufficient conditions for a solution to exist. We also consider the case where we have a complete graph instead of a complete bipartite graph. We show that the edge partitioning problem in a complete graph is at least as difficult as in a complete bipartite graph. We also give necessary and sufficient conditions for a solution to exist if E1 ∪ E2 form a tree or if they form a Hamiltonian cycle in the case of a complete graph. Finally we examine for both, complete and complete bipartite graphs, the case where each one of the sets E1 and E2 is structured (two disjoint Hamiltonian chains, two edge disjoint cycles) and present necessary and sufficient conditions.

We are interested in coloring the edges of a mixed graph. i.e., a graph containing unoriented and oriented edges. This problem is related to a communication problem in job-shop scheduling systems. In this paper we give general bounds oil the number of required colors and analyze the complexity Status of this problem. In particular, we provide N P-completeness results for the case of outerplanar graphs, as well as for 3-regular bipartite graphs (even when only 3 colors are allowed, or when 5 colors are allowed and the graph is fully oriented). Special cases admitting polynomial-time Solutions are also discussed. (C) 2008 Elsevier B.V. All rights reserved.