229 matches
-
nici în P nici NP-complete. Astfel de probleme se numesc probleme NP-intermediare. , și sunt exemple de probleme considerate a fi NP-intermediare. Acestea sunt unele dintre puținele probleme NP despre care nu se știe dacă sunt în P sau NP-complete. Problema izomorfismului grafurilor este problema computațională de a determina dacă două grafuri finite sunt . O importantă problemă nerezolvată în teoria complexității este dacă problema izomorfismului grafurilor este în P, NP-completă, sau NP-intermediară. Răspunsul nu este cunoscut, dar se crede că problema cel
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
unele dintre puținele probleme NP despre care nu se știe dacă sunt în P sau NP-complete. Problema izomorfismului grafurilor este problema computațională de a determina dacă două grafuri finite sunt . O importantă problemă nerezolvată în teoria complexității este dacă problema izomorfismului grafurilor este în P, NP-completă, sau NP-intermediară. Răspunsul nu este cunoscut, dar se crede că problema cel puțin nu este NP-completă. Dacă izomorfismul grafurilor ar fi NP-completă, s-ar plia la al doilea nivel. Deoarece se crede că ierarhia polinomială
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
a determina dacă două grafuri finite sunt . O importantă problemă nerezolvată în teoria complexității este dacă problema izomorfismului grafurilor este în P, NP-completă, sau NP-intermediară. Răspunsul nu este cunoscut, dar se crede că problema cel puțin nu este NP-completă. Dacă izomorfismul grafurilor ar fi NP-completă, s-ar plia la al doilea nivel. Deoarece se crede că ierarhia polinomială nu se pliază la niciun nivel finit, se crede că izomorfismul grafurilor nu este o problemă NP-completă. Cel mai bun algoritm pentru această
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
cunoscut, dar se crede că problema cel puțin nu este NP-completă. Dacă izomorfismul grafurilor ar fi NP-completă, s-ar plia la al doilea nivel. Deoarece se crede că ierarhia polinomială nu se pliază la niciun nivel finit, se crede că izomorfismul grafurilor nu este o problemă NP-completă. Cel mai bun algoritm pentru această problemă, datorat lui și , a rulat timp de 2 pentru un graf cu "n" noduri. este problema calculului a unui număr întreg dat. Formulată ca o problemă de
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]