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?

Risposte
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 :-D

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

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.