Decidibilità o indecidibiliità dei problemi NP
Salve, volevo porre questa domanda perchè mi è venuto un dubbio...pensando a Goldbach, alla primalità e ai problemi NP. Ho letto da qualche parte in questo forum che alcuni matematici stanno studiando la congettura di Goldbach in termini di indecidibilità. Il dubbio che mi è sorto è questo : Dato un linguaggio $L\in NP$ il problema di decisione $ x \in L$ è decidibile ? perchè ho come l'impressione che GOLDBACH sia un problema NP e questo sarebbe un controsenso sulla sua indecidibilità o sto dicendo delle cavolate?
Risposte
"nochipfritz":
Salve, volevo porre questa domanda perchè mi è venuto un dubbio...pensando a Goldbach, alla primalità e ai problemi NP. Ho letto da qualche parte in questo forum che alcuni matematici stanno studiando la congettura di Goldbach in termini di indecidibilità. Il dubbio che mi è sorto è questo : Dato un linguaggio $L\in NP$ il problema di decisione $ x \in L$ è decidibile ? perchè ho come l'impressione che GOLDBACH sia un problema NP e questo sarebbe un controsenso sulla sua indecidibilità o sto dicendo delle cavolate?
Non so cosa sia NP e non sono esperto di logica formale. Ho pero' chiacchierato spesso, ultimamente, con un logico vero a cui ho chiesto della congettura di Goldbach e ti riporto la sua risposta.
La congettura potrebbe essere indecidibile (nel senso che si potrebbe meta-dimostrare che non esiste una dimostrazione); in questo caso necessariamente la congettura sarebbe vera
(metamatematicamente) in quanto la sua falsita' equivale a produrre un controesempio e quindi una dimostrazione della falsita'.
Se ho capito bene
mmhhh..ecco...proprio questo concetto vorrei capire. La classe $NP$ è l'insieme dei linguaggi $L$ così definiti :
$L$ = { $x \in {0,1}$* : esiste un certificato $y \in {0,1}$* con $|y|=O(|x|^c)$, $c$ costante e un algoritmo di verifica polinomiale A tale che $A(x,y)=1$ }
Ora se noi, da questo momento in poi, indichiamo con $$ la rappresentazione binaria di un numero naturale $x$, l'insieme
$GOLDBACH$ = { $ \in {0,1}$* : $n$ è un numero naturale pari ed è somma di due numeri primi }
dovrebbe appartenere a NP. Infatti $GOLDBACH$ si può definire anche in questo modo :
$GOLDBACH$ = {$ \in {0,1}$* : esiste un certificato $ \in {0,1}$*, $y \leq n$ e $A(n, y)=1$}
dove l'algoritmo $A(n,y)$ è così definito...
$A(n,y)= PARI?(n) and PRIMO?(y) and PRIMO?(n-y)$
L'algoritmo $A(n, y)$ è polinomiale in quanto è stato dimostrato che l'algoritmo di primalità AKS è polinomiale rispetto alla dimensione di $n$, e quindi può essere adottato questo agoritmo per stabilire se un numero è primo. AKS $\in O(||^k)$ per qualche $k$.
Dunque se $GOLDBACH \in NP$ (forse sto sbagliando nel mio ragionamento...che ho fatto sopra...) , $GOLDBACH$ è decidibile o indecidibile?
$L$ = { $x \in {0,1}$* : esiste un certificato $y \in {0,1}$* con $|y|=O(|x|^c)$, $c$ costante e un algoritmo di verifica polinomiale A tale che $A(x,y)=1$ }
Ora se noi, da questo momento in poi, indichiamo con $
$GOLDBACH$ = { $
dovrebbe appartenere a NP. Infatti $GOLDBACH$ si può definire anche in questo modo :
$GOLDBACH$ = {$
dove l'algoritmo $A(n,y)$ è così definito...
$A(n,y)= PARI?(n) and PRIMO?(y) and PRIMO?(n-y)$
L'algoritmo $A(n, y)$ è polinomiale in quanto è stato dimostrato che l'algoritmo di primalità AKS è polinomiale rispetto alla dimensione di $n$, e quindi può essere adottato questo agoritmo per stabilire se un numero è primo. AKS $\in O(|
Dunque se $GOLDBACH \in NP$ (forse sto sbagliando nel mio ragionamento...che ho fatto sopra...) , $GOLDBACH$ è decidibile o indecidibile?
Mi dispiace ma non sono in grado di seguirti - dovrei aver studiato logica invece di analisi ....
Per la verita' non capisco se questo $NP$ sia un attributo di un linguaggio o di un enunciato, ma sara' colpa mia.
Ti ripeto pero' cio' che mi e' stato detto da un esperto:
1) non si puo' escludere che GOLDBACH dia indecidibile
2) se pero' (meta) dimostrassimo che GOLDBACH e' indecidibile avremmo automaticamente (meta) dimostrato che
GOLDBACH e' vera
la 2) dipende essenzialmente dal fatto che GOLDBACH e' della forma $\forall n P(n)$ dove $P$ e' "algoritmica" e
quindi la sua negazione e' $\exists n: non-P(n)$, che se e' vera e' automaticamente dimostrabile.
Tutto questo io l'ho capito "da esterno" del settore e quindi per precisazioni tecniche serve qualcuno piu' addentro di me.
Ciao
Per la verita' non capisco se questo $NP$ sia un attributo di un linguaggio o di un enunciato, ma sara' colpa mia.
Ti ripeto pero' cio' che mi e' stato detto da un esperto:
1) non si puo' escludere che GOLDBACH dia indecidibile
2) se pero' (meta) dimostrassimo che GOLDBACH e' indecidibile avremmo automaticamente (meta) dimostrato che
GOLDBACH e' vera
la 2) dipende essenzialmente dal fatto che GOLDBACH e' della forma $\forall n P(n)$ dove $P$ e' "algoritmica" e
quindi la sua negazione e' $\exists n: non-P(n)$, che se e' vera e' automaticamente dimostrabile.
Tutto questo io l'ho capito "da esterno" del settore e quindi per precisazioni tecniche serve qualcuno piu' addentro di me.
Ciao
Ti ringrazio lo stesso...e ti dico che è giusto come ragionamento logico....ho comqune deciso di scrivere questo mio ragionamento...per capire se sto sbagliando dicendo che Goldbach è decidibile (che per l'appunto non significa dimostrare la congettura). Quindi aspetto che qualcuno (che magari conosce bene la classe NP) , legga quello che ho scritto e possa ragionare insieme a me. Grazie lo stesso....per il tuo contributo.
nochipfritz, stai facendo semplicemente confusione su due modi distinti di definire il concetto di decidibilita'.
In logica, dire che Goldbach non e' decidibile significa che nell'Aritmetica di Peano non si puo' provare ne' Goldbach ne' la sua negazione.
La tua e' una corretta dimostrazione che Goldbach e' in NP, ma cio' non implica che Goldbach sia dimostrabile o refutabile nell'Aritmetica. Almeno, io non riesco a dimostrarlo; tu ci riesci?
In logica, dire che Goldbach non e' decidibile significa che nell'Aritmetica di Peano non si puo' provare ne' Goldbach ne' la sua negazione.
La tua e' una corretta dimostrazione che Goldbach e' in NP, ma cio' non implica che Goldbach sia dimostrabile o refutabile nell'Aritmetica. Almeno, io non riesco a dimostrarlo; tu ci riesci?
Ora è chiaro....sono 2 concetti di decidibilità diversi.
Però a questo punto mi chiedo ....Goldbach può essere dimostrato solo mediante la logica di Peano? Voglio dire....se bisogna dimostrare che un numero pari è somma di due numeri primi...può essere fatto anche in altri contesti, anche perchè un numero pari, così come un numero primo è un numero naturale...ma è anche un numero reale, così come può essere visto come un numero complesso dove la parte immaginaria è nulla o come sequenza di stringhe 0 e 1 facenti parte di un linguaggio binario.
Cioè nella teoria dei numeri, spesso ho visto risultati che riguardano numeri definibili con l'aritmetica di peano dimostrati con strumenti che vanno oltre l'aritmetica di peano . In fondo la stessa analisi matematica è nata con l'obiettivo di introdurre il concetto del continuo per trattare problemi che nel discreto sarebbero stati intrattabili.
Però a questo punto mi chiedo ....Goldbach può essere dimostrato solo mediante la logica di Peano? Voglio dire....se bisogna dimostrare che un numero pari è somma di due numeri primi...può essere fatto anche in altri contesti, anche perchè un numero pari, così come un numero primo è un numero naturale...ma è anche un numero reale, così come può essere visto come un numero complesso dove la parte immaginaria è nulla o come sequenza di stringhe 0 e 1 facenti parte di un linguaggio binario.
Cioè nella teoria dei numeri, spesso ho visto risultati che riguardano numeri definibili con l'aritmetica di peano dimostrati con strumenti che vanno oltre l'aritmetica di peano . In fondo la stessa analisi matematica è nata con l'obiettivo di introdurre il concetto del continuo per trattare problemi che nel discreto sarebbero stati intrattabili.
Allora, il sistema base dell'aritmetica e' l'Aritmetica di Peano del prim'ordine. Naturalmente essa e' notoriamente incompleta: non riesce nemmeno a dimostrare teoremi combinatori abbastanza semplici, tipo http://en.wikipedia.org/wiki/Paris–Harrington_theorem
Tuttavia gia' l'Analisi, reale o complessa, puo' essere codificata nell'Aritmetica di Peano del secondo ordine (dove si puo' quantificare su e parlare di insiemi infiniti di numeri naturali). Ricordati che i reali e i complessi, secondo l'approccio di Dedekind, sono insiemi di razionali, e i razionali a loro volta coppie di naturali e quindi codificabili come naturali; e analogamente le funzioni sono insiemi di naturali.
Naturalmente nulla ti vieta di usare la teoria degli insiemi ZFC, ma considera che l'Aritmetica di Peano del secondo ordine e' potentissima (credo che quasi tutta la teoria dei numeri, se non tutta, possa essere espressa in essa)
Tuttavia gia' l'Analisi, reale o complessa, puo' essere codificata nell'Aritmetica di Peano del secondo ordine (dove si puo' quantificare su e parlare di insiemi infiniti di numeri naturali). Ricordati che i reali e i complessi, secondo l'approccio di Dedekind, sono insiemi di razionali, e i razionali a loro volta coppie di naturali e quindi codificabili come naturali; e analogamente le funzioni sono insiemi di naturali.
Naturalmente nulla ti vieta di usare la teoria degli insiemi ZFC, ma considera che l'Aritmetica di Peano del secondo ordine e' potentissima (credo che quasi tutta la teoria dei numeri, se non tutta, possa essere espressa in essa)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo