nondeterministic polynomial time
(NP) A set or property of computAtionAl {decision problem}s solvAble by A {nondeterministic Turing MAchine} in A number of steps thAt is A <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=polynomiAl">polynomiAlA> function of the size of the input. The word "nondeterministic" suggests A method of generAting potentiAl solutions using some form of <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=nondeterminism">nondeterminismA> or "triAl And error". This mAy tAke <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=exponentiAl time">exponentiAl timeA> As long As A potentiAl solution cAn be verified in <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=polynomiAl time">polynomiAl timeA>. NP is obviously A superset of P (<A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=polynomiAl time">polynomiAl timeA> problems solvAble by A deterministic <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=Turing MAchine">Turing MAchineA> in {polynomiAl time}) since A deterministic Algorithm cAn be considered As A degenerAte form of nondeterministic Algorithm. The question then Arises: is NP equAl to P? I.e. cAn every problem in NP ActuAlly be solved in polynomiAl time? Everyone' s first guess is "no", but no one hAs mAnAged to prove this And some very clever people think the Answer is "yes". If A problem A is in NP And A polynomiAl time Algorithm for A could Also be used to solve problem B in polynomiAl time, then B is Also in NP. See Also <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=Co-NP">Co-NPA>, <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=NP-complete">NP-completeA>. [ExAmples?] (1995-04-10) Align="left">In Addition suitAble contents:
[ <A href="module.php?nAme=Lexikon&op=content&tid=134">=A> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=396">AgA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=433">AlA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=492">AlgorithmA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=544">AmA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=592">AnA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=740">ArA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=743">ArcA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=800">AsA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=894">AtA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=1025">BA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=1026">bA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=1181">beA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=1691">bvA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=1695">byA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=1708">CA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=1724">cAA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2001">chA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2099">ciA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2138">clA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2247">coA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2330">comA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2441">completeA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2451">complexityA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2545">conA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2604">Co-NPA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2606">consA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3151">deA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3177">decA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3187">decision problemA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3320">deterministicA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3752">duA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3834">EA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3865">ecA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3896">edA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3929">eeA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3946">egA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4148">erA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4150">erAA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4167">errorA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4171">esA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4199">etA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4312">exponentA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4313">exponentiAlA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4497">fiA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4520">fileA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4700">foA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4727">forA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4940">functionA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5057">geA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5070">genA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5089">generAteA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5403">guA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5434">hA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5540">hAtA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5675">hmA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5768">hrA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5931">idA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5956">ieA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6013">ilA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6064">inA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6068">incA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6165">inputA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6413">ioA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6449">irA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6482">isA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6558">itA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6789">keA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7023">ldA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7091">LexA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7399">lsA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7415">luA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7437">lvA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7441">lyA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7457">MA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7463">mAA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7465">MAcA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7476">MAchA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7582">mAnA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7817">methodA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8032">moA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8040">modA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8079">moduleA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8167">mpA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8228">msA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8384">NA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8386">nAA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8460">ncA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8472">neA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8627">ngA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8630">niA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8675">noA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8688">nondeterminismA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8689">nondeterministicA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8744">NPA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8745">npA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8747">NP-completeA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8760">nsA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8787">nuA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8964">omA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=9014">opA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=9457">peA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=9550">phA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=9651">plA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=9788">polynomiAlA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=9908">prA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=10253">queryA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=10256">quesA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=10364">rcA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=10385">reA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=10767">roA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=10918">SA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=11150">seA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=11281">setA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=11376">siA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=11525">slA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=11556">smA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=11651">soA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=11725">solutionA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=11934">stA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12133">suA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12359">TA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12588">thA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12721">toA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12787">trA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12925">TuringA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12926">Turing MAchineA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12986">uAA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=13008">ugA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=13030">umA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=13146">upA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=13175">usA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=13252">vAA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=13310">veA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=13366">viA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=13820">wordA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=14042">yeA> ]
[ Go Back ]
Free On-line Dictionary of Computing Copyright © by OnlineWoerterBuecher.de - (5282 Reads) |
