Decidibilità o indecidibilità dei problemi NP

[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?

[nochipfritz]

Forse dovrei porre questo quesito nel reparto "informatica" ?

[fields1]

"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.

[nochipfritz]

@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

[fields1]

"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'.