Problem szeregowania zadań o nieokreślonej złożoności

Witam,

coś googlowanie w tym temacie mi nie idzie. Szukam mianowicie przykładu problemu szeregowania zadań o otwartej złożoności obliczeniowej. Czyli takiego, którego aktualnie żadne obliczenia matematyczne nie umieściły w żadnej kategorii.

Pamiętam, że jest co najmniej kilkanaście takich problemów, jednak niestety nie mogę żadnego wyszukać o konkretnych wartościach (np. szeregowanie zadań na 2 procesorach jednorodnych, zadania o jednostkowym czasie wykonania, kryterium: długość uszeregowania).

Ma ktoś jakiś przykład w głowie?

Czyli takiego, którego aktualnie żadne obliczenia matematyczne nie umieściły w żadnej kategorii.

Nie ma takich problemów.

http://cpp0x.pl/dokumentacja​/problem-NP-Trudny/1219

Odnośnie szeregowania zadań jest dobra książka: Peter Brucker, Scheduling Algorithms, 2006..

Przykład problemu NP-Trudnego: O||Cmax. Inny przykład: O3||Cmax. Kolejne: O|no-wait|Cmax jak również O2|no-wait|Cmax.

W tej książce, którą Ci podałem jest bodajże tabelka klasyfikująca problemy szeregowania zadań.

Tabelka jest nawet tu na stronie w kursach ;)

W takim razie masz może pomysł co miał na myśli autor zadania w którym trzeba podać przykład "problem o otwartej (nieokreślonej) złożoności obliczeniowej"? Może to kwestia terminologii?

Ten sam człowiek podawał na wykładach przykłady problemów, których złożoności jeszcze nie udowodniono, ale niestety właśnie ich nie pamiętam.

Dzięki za tytuł, na pewno się nim zainteresuje.

 

Może przez określenie 'otwartych' problemów złożoności obliczeniowej chodziło o to, że nie przedstawiono dowodu na to, że nie da się danego problemu rozwiązać ze złożonością niższą niż ta, która wynika z dowodu :) Choć w zasadzie to próbuję coś wygooglać na temat "nieokreślonej" złożoności obliczeniowej i jak na razie jestem w martwym punkcie :P Nie masz wykładu w postaci elektronicznej? To by było wiadomo o co chodzi :)

/edit:
Znalazłem coś: http://www.cs.put.poznan.pl​/mkasprzak/akb/AKwB-wyklad8.pdf

Problemy o nieokreślonej złożoności obliczeniowej (problemy otwarte) rozwiązuje się jak problemy obliczeniowo trudne

i to wszystko :P

/edit2:
https://inf.ug.edu.pl/~stefan​/Papers/Reports/83-korzenie.pdf
Strona 34 i 35 może być Twoim punktem zaczepienia.

/edit3:
http://en.wikipedia.org/wiki​/Computational_complexity_theory#Important_open_problems

Lista znanych problemów NP-zupełnych jest bardzo długa: [11] przytacza ich ponad 90. Znalezienie dla któregokolwiek z nich algorytmu o wielomianowym asymptotycznym czasie działania, lub udowodnienie, że takiego algorytmu nie ma, obali lub potwierdzi hipotezę 1.47. Ale na razie już od r. 1971 stanowi ona otwarty problem, mimo że za jego rozwiązanie Clay Mathematical Institute ustanowił nagrodę w wysokości miliona dolarów.

Problemy NP-zupełne (NPC) to takie problemy klasy NP, że każdy inny problem klasy NP może zostać do nich zredukowany w czasie wielomianowym – rozwiązanie jednego takiego problemu w czasie wielomianowym oznaczałoby, że P = NP.

Pytanie, czy problemy NP zupełne można rozwiązywać w czasie wielomianowym, jest największą zagadką informatyki teoretycznej – matematyki obliczeniowej. Ciągle nie udowodniono nierówności P 6= N (nie udowodniono także przeciwnie – że P = NP)

Czyli rozumiem, że każdy problem NP-zupełny można traktować za otwarty? W sensie, nikt nie udowodnił, że nie jest możliwe rozwiązanie go w czasie wielomianowym? Czyli właściwie odpowiedzią na pytanie będzie dowolny problem NP-zupełny?

Z tego co wiem to w przypadku niektórych problemów NP-zupełnych udowodniono, że nie można ich rozwiązać w czasie wielomianowym.

http://cpp0x.pl/dokumentacja​/Teoria-zlozonosci-obliczeniowe​j​/1213
http://cpp0x.pl/dokumentacja​/problem-NP-Zupelny/1220
http://cpp0x.pl/kursy​/Teoria-w-Informatyce​/Zlozonosc-obliczeniowa​/Klasy-problemow-NP/430

Wydaje mi się, że problem NP-zupełny jest 'zupełny' bo dowiedziono, że nie da się rozwiązać problemu ze złożonością wielomianową oraz dowiedziono, że da się sprawdzić rozwiązanie w czasie wielomianowym (No ale mogę się mylić - strzelam :)).

 Ta teoria jest generalnie rzecz biorąc beznadziejnie opisana w Internecie i książkach. Wszędzie przepisywane są bezrozumnie regułki. Miesiąc siedziałem, aby zrozumieć co jest jakim problemem i co się w czym zawiera oraz jakie są niuanse między problemami NP.

Z tą 'nieokreśloną' złożonością obliczeniową byłbym ostrożny, bo być może autor tego hasła niekoniecznie może mieć na myśli problemy NP-Trudne.

/edit:
Poza tym nie sądzę, aby kiedykolwiek udowodniono, że P=NP z prostego powodu: jeżeli ktoś udowodni na konkretnym problemie, że da się go rozwiązać z lepszą złożonością obliczeniową to on po prostu wypadnie z puli problemów NP. Reszta zostanie nietknięta.

Wydaje mi się, że problem NP-zupełny jest 'zupełny' bo dowiedziono, że nie da się rozwiązać problemu ze złożonością wielomianową

W rzeczywistości problemy NP-zupełne to takie problemy C, które spełniają dwa warunki:
1. C należy do NP.
2. Każdy problem w NP można zredukować do C w czasie wielomianowym (czyli C należy do NP-hard).

Poza tym nie sądzę, aby kiedykolwiek udowodniono, że P=NP z prostego powodu: jeżeli ktoś udowodni na konkretnym problemie, że da się go rozwiązać z lepszą złożonością obliczeniową to on po prostu wypadnie z puli problemów NP. Reszta zostanie nietknięta.

Jeśli dany problem NP byłby problemem NP-zupełnym, to algorytm rozwiązujący go w czasie wielomianowym stanowiłby konkretny dowód, że P=NP, z powodu punktu 2.

lepszą złożonością obliczeniową

Tu nie chodzi o złożoność lepszą, tylko wielomianową. O(n^(9→9→9→9→9)) to złożoność wielomianowa — i gdyby znaleźć algorytm rozwiązania jakiegoś problemu NP-zupełnego o takiej złożoności to byłby to dowód, że P=NP — ale dla jakichkolwiek praktycznych zastosowań jest znacznie gorsza niż, dajmy na to, O(n! * 2^n). Z tego powodu to, czy P=NP, powinno interesować głównie matematyków chcących zgarnąć milion dolarów, a nie programistów.