NP-complete problem

NP-complete problem

      any of a class of computational problems for which no efficient solution algorithm has been found. Many significant computer-science problems belong to this class—e.g., the traveling salesman problem, satisfiability problems, and graph-covering problems.

      So-called easy, or tractable, problems can be solved by computer algorithms that run in polynomial time; i.e., for a problem of size n, the time or number of steps needed to find the solution is a polynomial function of n. Algorithms for solving hard, or intractable, problems, on the other hand, require times that are exponential functions of the problem size n. Polynomial-time algorithms are considered to be efficient, while exponential-time algorithms are considered inefficient, because the execution times of the latter grow much more rapidly as the problem size increases.

      A problem is called NP (nondeterministic polynomial) if its solution can be guessed and verified in polynomial time; nondeterministic means that no particular rule is followed to make the guess. If a problem is NP and all other NP problems are polynomial-time reducible to it, the problem is NP-complete. Thus, finding an efficient algorithm for any NP-complete problem implies that an efficient algorithm can be found for all such problems, since any problem belonging to this class can be recast into any other member of the class. It is not known whether any polynomial-time algorithms will ever be found for NP-complete problems, and determining whether these problems are tractable or intractable remains one of the most important questions in theoretical computer science. When an NP-complete problem must be solved, one approach is to use a polynomial algorithm to approximate the solution; the answer thus obtained will not necessarily be optimal but will be reasonably close.

* * *


Universalium. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Problem solving — forms part of thinking. Considered the most complex of all intellectual functions, problem solving has been defined as higher order cognitive process that requires the modulation and control of more routine or fundamental skills (Goldstein Levin …   Wikipedia

  • Complete bipartite graph — A complete bipartite graph with m = 5 and n = 3 Vertices n + m Edges mn …   Wikipedia

  • Complete (complexity) — In computational complexity theory, a computational problem is complete for a complexity class if it is, in a formal sense, one of the hardest or most expressive problems in the complexity class. If a problem has the property that it allows you… …   Wikipedia

  • Complete coloring — of the Clebsch graph with 8 colors. Every pair of colors appears on at least one edge. No complete coloring with more colors exists: in any 9 coloring some color would appear only at one vertex, and there would not be enough neighboring vertices… …   Wikipedia

  • Complete information — is a term used in economics and game theory to describe an economic situation or game in which knowledge about other market participants or players is available to all participants. Every player knows the payoffs and strategies available to other …   Wikipedia

  • Problem Frames Approach — Problem Analysis or the Problem Frames Approach is an approach to software requirements analysis. It was developed by British software consultant Michael A. Jackson. The Problem Frames Approach was first sketched by Jackson in his book Software… …   Wikipedia

  • Complete Works of Shakespeare — Complete Works of William Shakespeare is the standard name given to any volume containing all the plays and poems of William Shakespeare. Some editions include several works which were not completely of Shakespeare s authorship (collaborative… …   Wikipedia

  • Complete Savages — intertitle Genre Sitcom Created by …   Wikipedia

  • Complete lattice — In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet). Complete lattices appear in many applications in mathematics and computer science. Being a special instance of… …   Wikipedia

  • Complete mixing — In evolutionary game theory, complete mixing refers to an assumption about the type of interactions that occur between individual organisms. Interactions between individuals in a population attains complete mixing if and only if the probably… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”