Algorithm - NP Complete (Nondeterministic Polynomial Time Complete)

This is a class of problems that are so difficult that even the best solutions cannot consistently determine their solutions in an efficient way.

Specifically, NP Complete problems can only possibly be solved in polynomial time using a nondeterministic Turing machine (a computer capable of making guesses and checking them in polynomial time).

Because of the problem with finding the “best” solution, programs are often developed to find a usually reasonable solution.

Example

• weather prediction (there are just too many variables)
• how to fill a box with odd-sized objects,

Reference

Discover More
Algorithm

An is a (procedure|method) for solving a problem. If there exists an algorithm, the function that performs it is called computable. Study of algorithms dates at least to Euclid and were formalized by...
Online Analytical Processing (Olap)

Online Analytical Processing (OLAP) refers to: a class of application an approach to quickly answer multi-dimensional analytical queries. The term OLAP was created as a slight modification of...
Polynomial time algorithms

polynomial time algorithm. A problem that: can be solved in polynomial time is Tractable can NOT be solved in polynomial time is intractable A function f is a one-way if and only if it can...
Relational Data Modeling - View selection problem (recommending the best aggregation tables) - Data Warehousing

The View Selection Problem (VSP) is an NP-Complete problem. Challenges: Design Which materializations to create? Populate Load them with data Maintain Incrementally populate when data changes...
Tractable / Intractable Problem

Tractable: a problem that can be solved in polynomial time intractable: a problem that can NOT be solved in polynomial time the problems that can be solved by a computer using no more time than...
Traveling Saleman Problem (TSP)

The TSP is not NP Complete but NP hard. See AgentScript model No,...