შეგიძლიათ გაიხსენოთ, რა არის NP-შესრულებადი პრობლემა? როგორ განსხვავდება ის უბრალო NP-დან?

NP (ნედტერმინისტული პოლინომიური დრო) — ეს პრობლემების კლასი, რომლის გადაწყვეტილებასაც შეიძლება პოლინომიური დროით გადაამოწმება. ანუ, თუ გაქვთ პასუხის კანდიდატი, შეგიძლიათ სწრაფად გადაამოწმოთ, სწორია თუ არა.

NP-პოლნული პრობლემები — ეს NP-ის ქვექვსია, რომელიც ერთდროულად ყველაზე "რთული" ამ კლასში. თუ ვინმე იპოვიდა პოლინომიური ალგორითმს ნებისმიერი NP-პოლნული პრობლემის გადასაწყვეტად, მაშინ ყველა NP-ის პრობლემას შეიძლება პოლინომიური დროით გადაჭრა.

ძირითადი განსხვავება:

• NP — პრობლემები, რომელთა გადაწყვეტილების სწრაფად გადამოწმებაა შესაძლებელი.
• NP-პოლნული — NP-ის პრობლემები, რომელთაც შეიძლება სხვა ნებისმიერი NP-ის პრობლემის გადაყვანა (ანუ, ისინი "ყველაზე რთული" არიან NP-ში).

მაგალითი: გრაფში მაქსიმალური კლიკის პრობლემა NP-პოლნულია, ხოლო პრობლემა, თუ არის ქვექვსი ელემენტის ჯამი განსაზღვრულ რიცხვთან ტოლი, NP-შია.