Gio 22 Agosto, 18:32:14 - 2019

Autore Topic: complessità P vs NP  (Letto 530 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline scheggia89

  • Studente di Dottorato
  • ***
  • Post: 156
  • FeedBack: +3/-0
    • Mostra profilo
complessità P vs NP
« il: Ven 16 Febbraio, 17:37:32 - 2018 »
Ciao a tutti, ho alcuni dubbi sulla complessità di problemi, in particolari sulle sequenti due domande.

1. Che conseguenze avremo sul problema P verso NP se si dimostrasse che la complessità del problema 3-SAT è O(3log2n)?

2. Che conseguenze avremo sul problema P verso NP se si dimostrasse che la complessità del problema 3-SAT è O(nlog2n)?

Qualcuno può aiutarmi a rispondere alle domande? Data la NP-completezza di 3-SAT,  alla domanda 1. risponderei affermando che P e NP non coincidono. Nel punto 2. risponderei invece che P e NP coincidono, ma non ne sono molto sicuro.
« Ultima modifica: Ven 16 Febbraio, 19:04:29 - 2018 da scheggia89 »

Offline MarvinPuppets

  • Neo-Laureato
  • **
  • Post: 60
  • FeedBack: +2/-0
    • Mostra profilo
Re:complessità P vs NP
« Risposta #1 il: Dom 18 Febbraio, 16:28:13 - 2018 »
Prendi con le pinze quello che ti sto dicendo perché sono passati diversi anni da quando ho studiato per questo esame quindi potrei sbagliarmi.

Però a rigor di logica, sia O(3^log2n) che O(n^log2n) sono super-polinomiali, quindi (credo) non aggiungano nulla al problema P versus NP.

In particolare 1) è sub-esponenziale e 2) è quasi-polinomiale, comunque sono entrambi fuori da P (ma contenuti in NP), quindi la risposta *dovrebbe* essere che nel caso di dimostrassero quelle classi di complessità P != NP.

Offline scheggia89

  • Studente di Dottorato
  • ***
  • Post: 156
  • FeedBack: +3/-0
    • Mostra profilo
Re:complessità P vs NP
« Risposta #2 il: Dom 18 Febbraio, 18:56:43 - 2018 »
Prendi con le pinze quello che ti sto dicendo perché sono passati diversi anni da quando ho studiato per questo esame quindi potrei sbagliarmi.

Però a rigor di logica, sia O(3^log2n) che O(n^log2n) sono super-polinomiali, quindi (credo) non aggiungano nulla al problema P versus NP.

In particolare 1) è sub-esponenziale e 2) è quasi-polinomiale, comunque sono entrambi fuori da P (ma contenuti in NP), quindi la risposta *dovrebbe* essere che nel caso di dimostrassero quelle classi di complessità P != NP.
Ah ok, posso farti una domanda? Nel caso in cui si ponesse la stessa domanda ma nel caso di OMEGA(3^logn) e OMEGA(n^log n ?)

Offline MarvinPuppets

  • Neo-Laureato
  • **
  • Post: 60
  • FeedBack: +2/-0
    • Mostra profilo
Re:complessità P vs NP
« Risposta #3 il: Lun 19 Febbraio, 21:34:01 - 2018 »
Considerando che la notazione omega è il lower bound, direi che la risposta è la stessa, perché significa che non è possibile ottimizzare un problema al di sotto di quella classe.
« Ultima modifica: Lun 19 Febbraio, 21:38:33 - 2018 da MarvinPuppets »