Algorithm - NP Complete (Nondeterministic Polynomial Time Complete)

Sorting Quicksort Anim

About

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).

See also Tractable / Intractable Problem

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

Example

Reference





Discover More
Sorting Quicksort Anim
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...
Data System Architecture
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...
Sorting Quicksort Anim
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...
Data System Architecture
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...
Sorting Quicksort Anim
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...
Card Puncher Data Processing
Traveling Saleman Problem (TSP)

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



Share this page:
Follow us:
Task Runner