Hlavní navigace

Názor ke článku Chart parsing a NP-úplnost od stewe - tvrdenie ze .... NP-uplny (tj. v nejhorsim pripade...

  • 5. 4. 2012 10:45

    stewe (neregistrovaný)

    tvrdenie ze .... NP-uplny (tj. v nejhorsim pripade zrejme exponencialni) sa mi nezda dostatocne presne. Ja mam pocit, ze kazdy NP jazyk je exponencialny na deterministickom turingovom stroji, samozrejme ked sa bavime o casovej zlozitosti, a polynomialny na nedeterministickom. Mysleli ste to teda tak, ze algoritmus pre ten parsing -- ktory je simulovany na deterministickom vypoctovom modeli -- je v najhorsom pripade exponencialny?