Klasy NPproblemów

0

Zgadzacie się z tym grafem? ewentualnie jakieś uwagi?

np.png

wedle tego mogę rozumieć że stwierdzenie
NP-zupełne c NP-trude
jest błędne?

2

Graf jest z d**y i nie ma nic wspólnego z rzeczywistością.
P może być równe NP, tego nie wiemy. Wtedy też NP-zupełne byłyby oczywiście równe P oraz NP.
Ale załóżmy na chwilę że wiemy że P!=NP. Graf nadal jest z zły. Każdy problem NP-zupełny z definicji musi być NP-trudny (i zawierać sie w NP). A na tym grafie mamy problemy NP-zupełne nie będące NP-trudne, co zwyczajnie nie może być prawdą. Nie wiem skąd wziąłeś ten graf ;]

0

Taki jeden doktor habilitowany nam sprezentował na wykładzie.

0

To spytaj go o przykład problemu który jest NP-zupełny a jednocześnie nie jest NP-trudny w takim razie ;] Chętnie się dowiem cóż to za problem, który z definicji istnieć nie może.

0

Skoro w klasie NP zawarte są problemy P i NP-zupełne to skoro NP-zupełne = NP-trudne to mogę uznać że klasa NP-trudna jest zawarta w klasie NP? Co z klasami P-SPACE i NP-SPACE - mam uznać że w nich zawarte są wszystkie problemy?

0

A skad niby pomysł ze NP-zupełne = NP-trudne? o_O Każdy problem NP-zupełny musi być NP-trudny i należeć do klasy NP. Ale problemy NP-trudne wcale nie muszą być NP, muszą być tylko "przynajmniej tak trudne jak każdy problem NP". Problemy NP-trudne w ogóle nie muszą być rostrzygalne, nie muszą być nawet problemami klasy R.
Twój kolejny wniosek też nie ma sensu. P-SPACE i NP-SPACE to klasy problemów rozwiazywalnych w wielomianowej pamięci, ale są przecież problemy klasy EXP-SPACE które wymagaja wykładniczej pamięci i problemy NP-trudne mogą jak najbardziej takiej pamięci wymagać.

1 użytkowników online, w tym zalogowanych: 0, gości: 1