| 单词 | NP-Problem |
| 释义 | NP-ProblemA problem is assigned to the NP (nondeterministic Polynomial time) class if it is solvable in polynomial time by anondeterministic Turing Machine. (A nondeterministic Turing Machine is a ``parallel'' Turing Machinewhich can take many computational paths simultaneously, with the restriction that the parallel Turing machines cannotcommunicate.) A P-Problem (whose solution time is bounded by a polynomial) is always also NP. If a solution to an NPproblem is known, it can be reduced to a single P (Polynomial time) verification. Linear Programming, long known to be NP and thought not to be P, was shown to be P byL. Khachian in 1979. It is not known if all apparently NP problems are actually P. A problem is said to be NP-Hard if an Algorithm for solving it can be translated into onefor solving any other NP-problem problem. It is much easier to show that a problem is NP than to show that it isNP-Hard. A problem which is both NP and NP-Hard is called anNP-Complete Problem. See also Complexity Theory, NP-Complete Problem, NP-Hard Problem, P-Problem, Turing Machine
Borwein, J. M. and Borwein, P. B. Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity. New York: Wiley, 1987. Greenlaw, R.; Hoover, H. J.; and Ruzzo, W. L. Limits to Parallel Computation: P-Completeness Theory. Oxford, England: Oxford University Press, 1995. |
| 随便看 |
|
数学辞典收录了8975条数学词条，基本涵盖了常用数学知识及数学英语单词词组的翻译及用法，是数学学习的有利工具。