Decidibilità o indecidibilità 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
Forse dovrei porre questo quesito nel reparto "informatica" ?
"nochipfritz":
S perchè ho come l'impressione che GOLDBACH sia un problema NP e questo sarebbe un controsenso sulla sua indecidibilità o sto dicendo delle cavolate?
La seconda che hai detto

Se un linguaggio $L$ e' in NP, implica, per definizione, che esiste una macchina di Turing non deterministica che decide $L$. Ora, le macchine di Turing non deterministiche possono essere simulate tranquillamente da quelle deterministiche; di conseguenza, $L$ e' decidibile.
@filed: quindi se mi stai dicendo che $L$ è decidibile ...mi dai ragione, non torto!!! Io volevo dire proprio questo che $L$ è decidibile....
Ho scritto questa domanda anche nella sezione "informatica" . Potresti dare uno sguardo a ciò che ho scritto in quella sezione?
https://www.matematicamente.it/forum/dec ... 9132cb49b2
Ho scritto questa domanda anche nella sezione "informatica" . Potresti dare uno sguardo a ciò che ho scritto in quella sezione?
https://www.matematicamente.it/forum/dec ... 9132cb49b2
"nochipfritz":
Ho scritto questa domanda anche nella sezione "informatica" . Potresti dare uno sguardo a ciò che ho scritto in quella sezione?
https://www.matematicamente.it/forum/dec ... 9132cb49b2
Violando il regolamento... (niente duplicazione di topic, per favore)
Chiudo qui, e rispondo di la'.