NPn.²adj.

Brit.

/ˌɛnˈpiː/, U.S.

/ˌɛnˈpi/

Origin: Formed within English, as an initialism. Etymon: English nondeterministic polynomial time.

Etymology: Initialism < nondeterministic polynomial time: see nondeterministic adj. 2 and polynomial time n. at polynomial n. and adj. Compounds.

Mathematics and Computing.

The class of problems for which an algorithm exists for checking the correctness of solutions (reached by guessing or trial and error) in a length of time or number of steps which is a polynomial function of the size of the input. Frequently attributive or as adj.: designating such a problem, esp. one for which an algorithm producing a general solution in polynomial time is not known.In computational theory, NP represents the class of formal languages that can be recognized by a nondeterministic Turing machine in polynomial time. Interest is focused on the subdivision of this class containing the complex and intractable problems termed NP-complete (see Compounds), including the travelling salesman problem and the factorization of large integers, and on the conjecture that all NP problems could have polynomial-time algorithms (widely believed to be false, or perhaps indeterminable).

ΚΠ

1972 SIAM Jrnl. Computing 1 281 Any language in NP is ‘polynomially reducible’ to various languages accepted by deterministic linear bounded automata and hence by deterministic Turing machines operating in exponential time.

1981 Jrnl. Algorithms 2 385 For most problems in NP, the proof that they are in NP is immediate.

1989 R. Penrose Emperor's New Mind 144 Problems in NP which are not in P are regarded as being ‘intractable’ (i.e. though soluble in principle, they are ‘insoluble in practice’) for reasonably large n.

1994 New Scientist 2 July 15/1 Interesting problems in mathematics are rarely ‘easy’. Many of them, such as network problems and packing problems..have components that can be arranged in different ways and that belong to a class called non-deterministic polynomial, or NP, problems.

Compounds

NP-complete adj. designating a member of a class of complex and intractable NP problems which can be converted into any other problem of the same class, such that if an algorithm for its solution in polynomial time existed, it would be possible to solve all NP problems in polynomial time; (of a problem) both NP and NP-hard.

ΚΠ

1974 Proc. 6th Ann. ACM Symp. on Theory Computing 47/1 It is widely believed that showing a problem to be NP-complete is tantamount to proving its computational intractability. In this paper we show that a number of NP-complete problems remain NP-complete even when their domains are substantially restricted.

1998 Theoret. Computer Sci. 198 221 Contrary to..expectations, reachability turns out to be NP-complete. The NP-hardness proof is a straightforward reduction from the satisfiability problem for boolean formulas in conjunctive normal form.

NP-completeness n. the condition of a problem of being NP-complete.

ΚΠ

1976 Computing 16 263 (title) The NP-completeness of the bandwidth minimization problem.

1994 SIAM Rev. 36 157 The notion of NP-completeness has helped researchers in several fields to argue that some problems are intrinsically difficult to solve computationally.

NP-hard adj. designating an intractable problem (whether or not NP) which may be polynomially reduced to an NP-complete problem.

ΚΠ

1975 SIGACT News Jan. 26 Checking for Hamiltonian circuit in bipartite graphs is shown to be NP-hard.

1995 New Scientist 28 Oct. 42/1 If you do have an NP-hard problem to solve, there's no reason to throw in the towel—your problem may not be a worst-case instance at all.

NP-hardness n. the condition of being NP-hard.

ΚΠ

1980 European Jrnl. Operational Res. 4 270 We investigate the computational complexity of deterministic sequencing problems in which unit-time jobs have to be scheduled on a single machine subject to chain-like precedence constraints. NP-hardness is established for the cases in which the number of late jobs or the total weighted tardiness is to be minimized.

1997 Jrnl. Symbolic Logic 62 643 NP-hardness of the problem can be shown.

This is a new entry (OED Third Edition, December 2003; most recently modified version published online March 2022).

单词	np
释义	Npn.¹ Brit. /ˌɛnˈpiː/, U.S. /ˌɛnˈpi/ Origin: Formed within English, by clipping or shortening. Etymon: neptunium n. Etymology: Symbolic abbreviation for neptunium n. Chemistry. The element neptunium. ΚΠ 1942 in Jrnl. Amer. Chem. Soc. (1948) 70 1129/1 The corresponding chemical symbols would be Np and Pu. 1964 Oceangr. & Marine Biol. 2 facing p. 240 (table) Detection of fallout-radionuclides in marine organisms... ²³⁹Np. 1991 in Chem. Brit. 27 201/1 At first, because Np and Pu were like uranium, they expected a series of 14 uranides, analogous to the lanthanides. This is a new entry (OED Third Edition, December 2003; most recently modified version published online March 2022). NPn.²adj. Brit. /ˌɛnˈpiː/, U.S. /ˌɛnˈpi/ Origin: Formed within English, as an initialism. Etymon: English nondeterministic polynomial time. Etymology: Initialism < nondeterministic polynomial time: see nondeterministic adj. 2 and polynomial time n. at polynomial n. and adj. Compounds. Mathematics and Computing. The class of problems for which an algorithm exists for checking the correctness of solutions (reached by guessing or trial and error) in a length of time or number of steps which is a polynomial function of the size of the input. Frequently attributive or as adj.: designating such a problem, esp. one for which an algorithm producing a general solution in polynomial time is not known.In computational theory, NP represents the class of formal languages that can be recognized by a nondeterministic Turing machine in polynomial time. Interest is focused on the subdivision of this class containing the complex and intractable problems termed NP-complete (see Compounds), including the travelling salesman problem and the factorization of large integers, and on the conjecture that all NP problems could have polynomial-time algorithms (widely believed to be false, or perhaps indeterminable). ΚΠ 1972 SIAM Jrnl. Computing 1 281 Any language in NP is ‘polynomially reducible’ to various languages accepted by deterministic linear bounded automata and hence by deterministic Turing machines operating in exponential time. 1981 Jrnl. Algorithms 2 385 For most problems in NP, the proof that they are in NP is immediate. 1989 R. Penrose Emperor's New Mind 144 Problems in NP which are not in P are regarded as being ‘intractable’ (i.e. though soluble in principle, they are ‘insoluble in practice’) for reasonably large n. 1994 New Scientist 2 July 15/1 Interesting problems in mathematics are rarely ‘easy’. Many of them, such as network problems and packing problems..have components that can be arranged in different ways and that belong to a class called non-deterministic polynomial, or NP, problems. Compounds NP-complete adj. designating a member of a class of complex and intractable NP problems which can be converted into any other problem of the same class, such that if an algorithm for its solution in polynomial time existed, it would be possible to solve all NP problems in polynomial time; (of a problem) both NP and NP-hard. ΚΠ 1974 Proc. 6th Ann. ACM Symp. on Theory Computing 47/1 It is widely believed that showing a problem to be NP-complete is tantamount to proving its computational intractability. In this paper we show that a number of NP-complete problems remain NP-complete even when their domains are substantially restricted. 1998 Theoret. Computer Sci. 198 221 Contrary to..expectations, reachability turns out to be NP-complete. The NP-hardness proof is a straightforward reduction from the satisfiability problem for boolean formulas in conjunctive normal form. NP-completeness n. the condition of a problem of being NP-complete. ΚΠ 1976 Computing 16 263 (title) The NP-completeness of the bandwidth minimization problem. 1994 SIAM Rev. 36 157 The notion of NP-completeness has helped researchers in several fields to argue that some problems are intrinsically difficult to solve computationally. NP-hard adj. designating an intractable problem (whether or not NP) which may be polynomially reduced to an NP-complete problem. ΚΠ 1975 SIGACT News Jan. 26 Checking for Hamiltonian circuit in bipartite graphs is shown to be NP-hard. 1995 New Scientist 28 Oct. 42/1 If you do have an NP-hard problem to solve, there's no reason to throw in the towel—your problem may not be a worst-case instance at all. NP-hardness n. the condition of being NP-hard. ΚΠ 1980 European Jrnl. Operational Res. 4 270 We investigate the computational complexity of deterministic sequencing problems in which unit-time jobs have to be scheduled on a single machine subject to chain-like precedence constraints. NP-hardness is established for the cases in which the number of late jobs or the total weighted tardiness is to be minimized. 1997 Jrnl. Symbolic Logic 62 643 NP-hardness of the problem can be shown. This is a new entry (OED Third Edition, December 2003; most recently modified version published online March 2022). > as lemmas N.P. N.P. n. = notary public at notary n. 1b. Π 1581 in C. C. Harvey Cal. Writs Yester House (1930) 228 Certified transcript..from the skrowis and prothogall of um. David Kingorne, N.P. 1916 Amer. Jrnl. Internat. Law 10 iv. 374 Given under my hand this 19th day of November, 1915. L. B. Foster, N. P. 2000 Shape Oct. 148/1 Everything's your fault. This is called personalization, says Harvard's Peg Baim, M.S., N.P. extracted from Nn. NP NP n. Grammar noun phrase. ΚΠ 1956 IRE Trans. Information Theory 2 116/2 Syntactic description is given in terms of what is called ‘immediate constituent analysis’. In description of this sort the words of a sentence are grouped into phrases,..classified as noun phrases (NP), verb phrases (VP) etc. 1972 R. M. W. Dixon Dyirbal Lang. N. Queensland v. 211 One final constituent of an NP which has not been dealt with above is a modifier noun. 1995 Appl. Linguistics 16 449 An explanation of choice between pronoun and full NP in expository texts. extracted from Nn. NP Categories » NP n. Mathematics and Computing (see NP n.²). extracted from Nn. n.p. n.p. n. (of a book) no printer, no publisher; no place; not paginated. ΚΠ 1882 S. Halkett & J. Laing Dict. Anon. & Pseudonymous Lit. Great Brit. I. 122/1 Answer to the Declaration published by the Archbishop of Canterbury... n.p., n.d. Octavo. Pp. 12. a1912 W. T. Rogers Dict. Abbrev. (1913) 137/1 n.p., no place (no printer's name). 1952 J. Carter ABC for Book-collectors 124 No place, no printer, no publisher (indiscriminately or collectively shortened to n.p.). 1966 Dawson's of Pall Mall Catal. No. 162. 12 Cicero..Laelius de amicitia. (n.p., n.d.) (Cologne..about 1467). 1969 N. B. Eales Cole Libr. of Early Med. & Zool. 330 The Complete Dictionary of Arts and Sciences... 2 vols. Fr., [4], vi, n.p. Pls. 1–11, 14–35, 40–42. extracted from Nn. < n.¹1942n.²adj.1972 as lemmas
随便看	acousto-optically acousto-optics acoustoelectric acoustoelectricity acoustoelectronic acoustoelectronics acoustooptic acoustooptical acoustooptically acoustooptics acover acovering acoy acp acqua alta acquaint acquaintable acquaintance acquaintance rape acquaintanced acquaintances acquaintanceship acquaintanceships acquaintancy acquaintant

Npn.1

NPn.2adj.

Compounds

> as lemmas

Npn.¹

NPn.²adj.