Tæki sem getur notað reglur og inntak til að ákvarða niðurstöðu, þó að það tæki sé tilgátulegt, er kallað hvað? Skrifaðu svarið í samhengi við fyrri spurningu. Það geta verið 1 - 20 setningar. Umfjöllun:
Skilgreiningarflokkur P er oft litið á sem stærðfræðilega framsetningu sem líkir þeim reikniverkefnum sem viðurkenna skilvirkan algoritma. Þessi tilgáta er kölluð Cobham-Edmonds fræðigreinin. Kompleksitækjastofninn NP, á hinn bóginn, inniheldur mörg vandamál sem fólk vill leysa á skilvirkan hátt, en fyrir sem engin skilvirk algoritmi er þekkt, svo sem Boolean fullnægjandi vandamál, Hamiltonian leið vandamál og vertex cover vandamál. Þar sem ákveðnar Turing vélar eru sérstakar, óákveðnar Turing vélar er auðvelt að sjá að hvert vandamál í P er einnig meðlimur í flokki NP.