12/01/2012, 18:54
12/01/2012, 23:20
13/01/2012, 00:25
13/01/2012, 09:43
Cosa ne pensi se io dicessi che un linguaggio logico L è turing-compl se esiste una riduzione dal linguaggio universale ad L? (non l ho letto da nessuna parte, è solo una mia idea).
a lezione il prof ha detto che la logica del prim'ordine è completa perchè possiamo associare i simboli di costante ai simboli sul nastro di una macchina di T, i predicati agli stati della macchina, e i funtori al nastro della macchina stessa. A me questo ragionamento, benchè sia comprensibile, risulta un pò oscuro.
13/01/2012, 14:37
13/01/2012, 15:03
Dirk_Pitt ha scritto:Approffitto della tua pazienza per chiederti qui una cosa diversa, anche se dovrei aprire un altra discussione: quando si parla di entailment classico ci si riferisce alla determinazione di un assegnamento valido per le variabili in una formula proposizionale CNF (ovvero SAT)?
Dirk_Pitt ha scritto:Inoltre se assumiamo che le clausole abbiano un numero massimo fissato di letterali questo come influisce sulla complessità del problema?
13/01/2012, 15:33
Sinceramente non lo so. Io "entailment" l'ho sempre sentito usare per la nozione di conseguenza logica
Stai parlando di SAT? Se sì è facile dimostrare che il problema di decidere la soddisfacibilità di formule con clausole di al più tre elementi (3SAT) è ancora NP-completo. 2SAT invece è risolvibile in tempo polinomiale.
13/01/2012, 16:50
14/01/2012, 01:14
14/01/2012, 09:19
Dirk_Pitt ha scritto:No, scusa ho scritto in modo confuso; mi riferivo all'entailment. Non capisco in che modo fissare il numero di letterali per clausola incida sulla complessità, o meglio, lo capisco ma in ogni caso la complessità deve dipendere anche dal numero di clausole, e non solo dalla loro lunghezza, o sbaglio?.
In ogni caso, se applico la risoluzione a due clausole di n ed m letterali, quante clausole si generano al max? Dato che si genera una clausola per ogni coppia di letterali complementari, e il numero di tali coppie è al massimo min(n,m) direi che è proprio questo il numero cercato. È corretto?
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.
Powered by phpBB © phpBB Group - Privacy policy - Cookie privacy
phpBB Mobile / SEO by Artodia.