[algorithm] What is an NP-complete in computer science?

The definitions for NP complete problems above is correct, but I thought I might wax lyrical about their philosophical importance as nobody has addressed that issue yet.

Almost all complex problems you'll come up against will be NP Complete. There's something very fundamental about this class, and which just seems to be computationally different from easily solvable problems. They sort of have their own flavour, and it's not so hard to recognise them. This basically means that any moderately complex algorithm is impossible for you to solve exactly -- scheduling, optimising, packing, covering etc.

But not all is lost if a problem you'll encounter is NP Complete. There is a vast and very technical field where people study approximation algorithms, which will give you guarantees for being close to the solution of an NP complete problem. Some of these are incredibly strong guarantees -- for example, for 3sat, you can get a 7/8 guarantee through a really obvious algorithm. Even better, in reality, there are some very strong heuristics, which excel at giving great answers (but no guarantees!) for these problems.

Note that two very famous problems -- graph isomorphism and factoring -- are not known to be P or NP.

Examples related to algorithm

How can I tell if an algorithm is efficient? Find the smallest positive integer that does not occur in a given sequence Efficiently getting all divisors of a given number Peak signal detection in realtime timeseries data What is the optimal algorithm for the game 2048? How can I sort a std::map first by value, then by key? Finding square root without using sqrt function? Fastest way to flatten / un-flatten nested JSON objects Mergesort with Python Find common substring between two strings

Examples related to language-agnostic

IOException: The process cannot access the file 'file path' because it is being used by another process Peak signal detection in realtime timeseries data Match linebreaks - \n or \r\n? Simple way to understand Encapsulation and Abstraction How can I pair socks from a pile efficiently? How do I determine whether my calculation of pi is accurate? What is ADT? (Abstract Data Type) How to explain callbacks in plain english? How are they different from calling one function from another function? Ukkonen's suffix tree algorithm in plain English Private vs Protected - Visibility Good-Practice Concern

Examples related to mathematical-optimization

How to interpret "loss" and "accuracy" for a machine learning model What is an NP-complete in computer science?

Examples related to theory

while-else-loop Using IS NULL or IS NOT NULL on join conditions - Theory question Why are C++ inline functions in the header? Difference Between Cohesion and Coupling What is a database transaction? What good are SQL Server schemas? How to program a fractal? What is an NP-complete in computer science? Way to go from recursion to iteration What's "P=NP?", and why is it such a famous question?

Examples related to np-complete

What are the differences between NP, NP-Complete and NP-Hard? What is an NP-complete in computer science? What's "P=NP?", and why is it such a famous question?