**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-completeness

Summary

In computational complexity theory, a problem is NP-complete when:
# It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no".

# When the answer is "yes", this can be demonstrated through the existence of a short (polynomial length) solution.

# The correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions.

# The problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified.

The name "NP-complete" is short for "nondeterministic polynomial-time complete". In this name, "nondeterministic" refers to no

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

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related people (16)

Related units (11)

Related publications (100)

Loading

Loading

Loading

Related concepts (73)

Computational complexity theory

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each ot

P versus NP problem

The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solve

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

Related courses (43)

CS-250: Algorithms

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, major algorithmic paradigms such as dynamic programming, sorting and searching, and graph algorithms.

COM-501: Advanced cryptography

This course reviews some failure cases in public-key cryptography. It introduces some cryptanalysis techniques. It also presents fundamentals in cryptography such as interactive proofs. Finally, it presents some techniques to validate the security of cryptographic primitives.

PHYS-467: Machine learning for physicists

Machine learning and data analysis are becoming increasingly central in sciences including physics. In this course, fundamental principles and methods of machine learning will be introduced and practised.

The problem of determining whether a graph G contains a threshold subgraph containing at least h edges is shown to be NP-complete if h is part of the input as the problems of minimum threshold completion, weighted 2-threshold partition and weighted 2-threshold covering. We also prove that the k-cyclic scheduling problem is NP-complete for all fixed k, a result used to show that deciding whether a threshold r-hypergraph contains a Hamiltonian cycle is NP-complete

1994L'Albanie a connu ces dernières années de profonds changements sociaux, économiques et urbains. A la chute du communisme, la répartition des populations sur le territoire a complètement changé, guidée non plus par un pouvoir central, mais par le désir de chacun. La région entre Tirana, l'aéroport et le plus grand port du pays s'est transformée dans sa morphologie, sa densité et sa logique spatiale. Cette région auparavant non bâtie, apparaît aujourd'hui comme une banane de sprawl continu. Ces transformations sont visibles dans la capitale. Son dessin exprime un centre constitué de longue date et une périphérie en « sédimentation » actuellement. Pour répondre à cette transformation, il est aujourd'hui essentiel de penser les transports publics qui irrigueront le territoire ces prochaines années. En réfléchissant au système ferroviaire comme centre linéaire générateur du développement de la région, nous pensons offrir un outil de développement durable. Les gares et arrêts, sortes de perles le long d'un collier ou de pôles hyper-connectés, sont les épicentres du développement futur des villes mais aussi des régions qui les entourent. La gare de Tirana se situe à la limite entre le centre et les zones informelles, au croisement de l'axe monumental et du ring. Cette gare offre l'occasion de condenser des problématiques à la fois liées à la région, la ville et le quartier où elle s'implante. Elle doit trouver une forme et une expression architecturale qui lui soient propres.

2009Related lectures (71)

Let K be a field with char(K) ≠ 2. The Witt-Grothendieck ring (K) and the Witt ring W (K) of K are both quotients of the group ring ℤ[𝓖(K)], where 𝓖(K) := K*/(K*)2 is the square class group of K. Since ℤ[𝓖(K)] is integral, the same holds for (K) and W(K). The subject of this thesis is the study of annihilating polynomials for quadratic forms. More specifically, for a given quadratic form φ over K, we study polynomials P ∈ ℤ[X] such that P([φ]) = 0 or P({φ}) = 0. Here [φ] ∈ (K) denotes the isometry class and {φ} ∈ W(K) denotes the equivalence class of φ. The subset of ℤ[X] consisting of all annihilating polynomials for [φ], respectively {φ}, is an ideal, which we call the annihilating ideal of [φ], respectively {φ}. Chapter 1 is dedicated to the algebraic foundations for the study of annihilating polynomials for quadratic forms. First we study the general structure of ideals in ℤ[X], which later on allows us to efficiently determine complete sets of generators for annihilating ideals. Then we introduce a more natural setting for the study of annihilating polynomials for quadratic forms, i.e. we define Witt rings for groups of exponent 2. Both (K) and W(K) are Witt rings for the square class group 𝓖(K). Studying annihilating polynomials in this more general setting relieves us to a certain extent from having to distinguish between isometry and equivalence classes of quadratic forms. In Section 1.1 we study the structure of ideals in R[X], where R is a principal ideal domain. For an ideal I ⊂ R[X] there exist sets of generators, which can be obtained in a natural way by considering the leading coefficients of elements in I. These sets of generators are called convenient. By discarding super uous elements we obtain modest sets of generators, which under certain assumptions are minimal sets of generators for I. Let G be a group of exponent 2. In Section 1.2 we study annihilating polynomials for elements of ℤ[G]. With the help of the ring homomorphisms Hom(ℤ[G],ℤ) it is possible to completely classify annihilating polynomials for elements of ℤ[G]. Note that an annihilating polynomial for an element f ∈ ℤ[G] also annihilates the image of f in any quotient of ℤ[G]. In particular, Witt rings for G are quotients of ℤ[G]. In Section 1.3 we use the ring homomorphisms Hom(ℤ[G],ℤ) to describe the prime spectrum of ℤ[G]. The obtained results can then be employed for the characterisation of the prime spectrum of a Witt ring R for G. Section 1.4 is dedicated to proving the structure theorems for Witt rings. More precisely, we generalise the structure theorems for Witt rings of fields to the general setting of Witt rings for groups of exponent 2. Section 1.5 serves to summarise Chapter 1. If R is a Witt ring for G, then we use the structure theorems to determine, for an element x ∈ R, the specific shape of convenient and modest sets of generators for the annihilating ideal of x. In Chapter 2 we study annihilating polynomials for quadratic forms over fields. More specifically, we first consider fields K, over which quadratic forms can be classified with the help of the classical invariants. Calculations involving these invariants allow us to classify annihilating ideals for isometry and equivalence classes of quadratic forms over K. Then we apply methods from the theory of generic splitting to study annihilating polynomials for excellent quadratic forms. Throughout Chapter 2 we make heavy usage of the results obtained in Chapter 1. Let K be a field with char(K) ≠ 2. Section 2.1 constitutes an introduction to the algebraic theory of quadratic forms over fields. We introduce the Witt-Grothendieck ring (K) and the Witt ring W(K), and we show that these are indeed Witt rings for 𝓖(K). In addition we adapt the structure theorems to the specific setting of quadratic forms. In Section 2.2 we introduce Brauer groups and quaternion algebras, and in Section 2.3 we define the first three cohomological invariants of quadratic forms. In particular we use quaternion algebras to define the Clifford invariant. In Section 2.4 we begin our actual study of annihilating polynomials for quadratic forms. Henceforth it becomes necessary to distinguish between isometry and equivalence classes of quadratic forms. We start by classifying annihilating ideals for quadratic forms over fields K, for which (K) and W(K) have a particularly simple structure. Subsequently we use calculations involving the first three cohomological invariants to determine annihilating ideals for quadratic forms over a field K such that I3(K) = {0}, where I(K) ⊂ W(K) is the fundamental ideal. Local fields, which are a special class of such fields, are studied in Section 2.5. By applying the Hasse-Minkowski Theorem we can then determine annihilating ideals of quadratic forms over global fields. Section 2.6 serves as an introduction to the elementary theory of generic splitting. In particular we introduce Pfister neighbours and excellent quadratic forms, which are the subjects of study in Section 2.7. We use methods from generic splitting to study annihilating polynomials for Pfister neighbours. The obtained result can be applied inductively to obtain annihilating polynomials for excellent quadratic forms. We conclude the section by giving an alternative, elementary approach to the study of annihilating polynomials for excellent forms, which makes use of the fact that (K) and W(K) are quotients of ℤ[𝓖(K)].