Stiamo facendo manutenzione.

Cazzeggiando sui teoremi…

Se non trovi un'altra area per la tua discussione, ma pensi che questa possa essere di interesse comune, questa è l'area adatta.
Rispondi
Avatar utente
Aspie96
Amministratore
Messaggi: 1386
Iscritto il: 23/02/2019, 19:52

Cazzeggiando sui teoremi…

Messaggio da Aspie96 » 13/03/2015, 20:32

Ci ho pensato ora.

Immaginate che per ogni problema di un certo tipo (non meglio specificato) si possa individuare un insieme finito di elementi nel quale è contenuta la soluzione.
Il metodo per trovarla è funzionante ed è dimostrabile tramite un teorema.

Ora io vi chiedo: dimostratemi che è possibile trovare la soluzione (che è univoca) anche senza provare tutte le soluzioni degli elementi e provate a dimostrarlo senza effettivamente spiegare come si trova la soluzione (ma soltanto dimostrando che è possibile trovarla in altro modo, senza specificare quale, insomma).

EDIT: Aggiungo: data una soluzione è possibile verificare con facilità se si tratta di quella corretta.
francesco.aliotta
Messaggi: 812
Iscritto il: 09/07/2014, 16:33

Re: Cazzeggiando sui teoremi…

Messaggio da francesco.aliotta » 19/03/2015, 17:40

Ho visto ora questo tuo post.
Non sono però certo di aver capito la domanda.
Provo a spiegarmi.
1) Le premesse sono che il problema è risolubile. Almeno, tu dici che il metodo per trovare la soluzione esiste ed è funzionante. Ne deduco che, qualunque sia il problema si tratta di un problema di Classe P.
2) La tua nota finale, ci informa che una volta trovata la soluzione è possibile adottare una procedura relativamente semplice per verificarne la validità. Il che ci dice che è un problema di classe NP. Ma la nota non aggunge in verità nulla dato che ognni problema di classe P è, per definizione, anche di classe NP.

Quindi ne deduco definitivamente che il problema è di Classe P=NP e che una macchina deterministica di Touring ne può produrre la soluzione.
Ma il tuo problema non è questo. Questo è implicito nelle premesse. Tu, se ho compreso bene, cerchi una procedura che fornisca la soluzione evitando di esplorare le soluzioni di tutti gli elementi che costituisco l'insieme in cui è contenuta la soluzione. Il problema è quindi quello di abbassare la complessità algoritmica per la soluzione di un problema NP-completo.
Ho compreso bene?
Se ho compreso bene si tratta di minimizzare il grafo che porta dal nodo iniziale a quello finale. Ma se la vedo in questa maniera non ho altro modo che provare a formulare un algoritmo non deterministico. In linea di principio, posso simulare una macchina non deterministica su una macchina di Touring deterministica. Ma, se lo facessi la computazione deterministica di tutte le computazioni ramificate andrebbe in tempo esponenziale.
In sintesi, mi sembrerebbe che la risposta alla tua domanda richiederebbe una macchina di Touring non deterministica.
Ho compreso bene la tua domanda o ti ho completamente frainteso e volevi dire qualche altra cosa?

Questa volta sei tu che devi avere pazienza con me. Come sai non sono un'iformatico. Ho cercato di capire cosa un'informatico volesse dire ma mi rendo conto benissimo del fatto che potrei avere preso le fantomatiche lucciole per lanterne!
Avatar utente
Aspie96
Amministratore
Messaggi: 1386
Iscritto il: 23/02/2019, 19:52

Re: Cazzeggiando sui teoremi…

Messaggio da Aspie96 » 20/03/2015, 16:11

francesco.aliotta ha scritto:Tu, se ho compreso bene, cerchi una procedura che fornisca la soluzione evitando di esplorare le soluzioni di tutti gli elementi che costituisco l'insieme in cui è contenuta la soluzione.

Più o meno.
Io non voglio sapere come trovare la soluzione (impossibile, visto che il problema non è specificato), ma solo la dimostrazione che esiste un metodo per farlo.

Ovviamente io lo so già, è solo un'idea che mi è venuta in mente.
La soluzione è in parte molto, molto deludente e per trovarla è necessario interpretare alla lettera ciò che ho scritto nel primo post.
Non è necessaria una macchina non deterministica.
francesco.aliotta
Messaggi: 812
Iscritto il: 09/07/2014, 16:33

Re: Cazzeggiando sui teoremi…

Messaggio da francesco.aliotta » 20/03/2015, 18:22

Non so, se prendo alla lettera il tuo post dovrei dire che so immediatamente che la soluzione è contenuta in un insieme finito di N elementi.

A questo punto, non dovrei far altro che provare gli N elementi uno dopo l'altro. Se sono sfortunato andrò avanti con le prove sino al tentativo N-1. Anche se avrò fallito, a questo punto saprò che la soluzione sta nell'elemento N, senza necessità di provarne la correttezza.

Così ho dimostrato che è, letteralmente, possibile trovare la soluzione senza effettuare tutte le N prove. Anzi, ho dimostrato che certamente non occorre effettuare N prove.

Ho provato a prenderti rigorosamente alla lettera. Se è questo ciò che volevi dire, sono d'accordo che è deludente. Pensavo che volessi proporre un problema più intrigante, tipo la minimizzazione del numero delle mosse.
Avatar utente
Aspie96
Amministratore
Messaggi: 1386
Iscritto il: 23/02/2019, 19:52

Re: Cazzeggiando sui teoremi…

Messaggio da Aspie96 » 20/03/2015, 20:15

Il problema era appunto sulla questione dell'interpretazione e direi che è stato risolto egregiamente.

Si collega alla discussione sull'interpretazione e ad altre sul forum.

Ovviamente non avrei potuto metterla come commento ad una di quelle, sarebbe stato ovvio.

Sappiamo inoltre che esistono infiniti altri algoritmi per trovare la soluzione corretta.
In molti casi, quello appena proposto è il migliore, ma in moltissimi altri no.
Quindi sappiamo che ci sarà sempre un modo per farlo.
Rispondi