È questo finito grafico problema decidibile? Quali fattori rendono un problema decidibile?

Question

Voglio sapere se il seguente problema è decidibile e come scoprire. Ogni problema che vedo posso dire "sì" o "no" ad esso, quindi sono più problemi e algoritmi decidibile tranne pochi (che è fornito qui )?

Input: un diretto e finito grafico $ G $, con $ v $ e $ u $ come vertici
Domanda: Fa un percorso in $ G $ con $ u $ come vertice iniziale e $ v $ come esistono finale vertice

Answer 1

Qualunque problema che richiede solo l'esame di una quantità limitata di dati è decidibile, perché c'è un algoritmo che consiste di enumerare tutte le possibili soluzioni. Può essere incredibilmente lento, ma non è rilevante:. Se c'è un algoritmo, è decidibile

Il problema si Stato assume un grafo finito, che suggerisce con forza che è decidibile. A rigor di termini, è necessario guardare un po 'oltre. Il problema è una proprietà sui sentieri nel grafico, e non v'è talvolta un numero infinito di percorsi, quando il grafico contiene un ciclo (è possibile ad anello intorno a questo ciclo di tutte le volte che volete). Tuttavia, è facile girare il problema ad un problema finita: se c'è un percorso che inizia con $ u $ e termina con $ v $ che comprende un ciclo, allora si può tagliare fuori tutti i cicli di quel percorso, e si dispone di un nuova soluzione che non include un ciclo. Poiché v'è un numero finito di percorsi che non comportano un ciclo (se il grafico ha $ k $ bordi, ci sono al massimo $ k! $ Percorsi che non utilizzano lo stesso bordo più di una volta), il problema di trovare un percorso da $ u $ a $ v $ è finitario, quindi decidibile.

Per inciso, questa proprietà è chiamata connettività .

Questo approccio è comune, chiamato riduzione . Dato un problema che non è semplice, abbiamo ridotto a un problema che sapevamo come risolvere.

Spesso è difficile dimostrare che un problema è indecidibile. Per dimostrare che un problema è decidibile, tutto quello che dobbiamo fare è esporre un algoritmo che decide. Per dimostrare che un problema è indecidibile, abbiamo bisogno di dimostrare che nessun algoritmo può esistere. Ci sono alcuni problemi indecidibili ben noti. In pratica, la maggior parte del tempo, quando si dimostra che un problema è indecidibile, mostriamo che c'è un problema indecidibile noto che riduce al nostro problema. Dal momento che un algoritmo per il nostro problema sarebbe risolvere il noto problema indecidibile, il nostro problema deve anche essere indecidibile.

non si può davvero dire che “la maggior parte dei” problemi sono decidibili o problemi “la maggior parte” sono indecidibili. In un certo senso teorico, quasi tutti i problemi sono indecidibile, ma abbiamo una forte tendenza per affrontare i problemi “interessanti”, e questi sono più probabilità di avere una soluzione.

Answer 2

Il problema è banalmente decidibile, come sottolineato da Gilles in un commento. Per quanto riguarda l'altra domanda ...

sono la maggior parte dei problemi e algoritmi decidibile tranne pochi (che è fornito qui )?

No. In realtà, la maggior parte problemi sono indecidibili. In realtà, ci sono molti problemi numerabile (lingue), ma ci sono solo numerabile molte macchine Turing, che significa che ci sono al massimo molti problemi decidibili numerabili.

Answer 3

Sì, questo è decidibile, perché si può fare una ricerca esaustiva di tutti i percorsi possibili. Non c'è bisogno di guardare i percorsi che si ripetono un vertice, dal momento che la "deviazione" potrebbe essere saltato. Ma la lunghezza di qualsiasi percorso non ripetitivo è delimitata dalle dimensioni del grafico, che è finito, e quindi ci sono solo un numero finito di tali percorsi, che possono essere controllati singolarmente.

Quello che non è decidibile è la seguente: dato un grafo infinita $ G $ e due vertici $ A $ e $ B $, decidere se c'è un percorso da $ a $ a $ b $. Questo non è decidibile se il grafico è dato come oracolo ed è anche non decidibile se il grafico è dato attraverso un programma che calcola esso.

Answer 4

Non esiste un metodo che ti dice se un problema specifico è decidibile o meno. Con il tempo, si potrebbe ottenere un buon "sospetto" o meno di un problema specifico è decidibile.

Quello che di solito è il seguente:

1. cercare di risolvere il problema. Cioè, cercare di pensare ad un programma per computer che risolve il problema dato. Per il vostro problema suggerito - un programma molto semplice vi basta controllare qualsiasi percorso possibile, e quindi sarà sempre riuscirà a trovarlo (se esiste), o dirti alcun percorso esiste altro modo.
2. formulare chiaramente il problema. Molti problemi sono troppo vaghi, ma quando scritto chiaramente è molto facile vedere se decidibile o no (confrontando ad altri problemi, noti per essere un / decidibile, o utilizzando metodi noti come Rice's teorema )
3. Se (2) non ha funzionato, ma è ancora ritengono che il problema è indecidibile, provare a dimostrarlo la riduzione da un problema indecidibile (problema della terminazione (o il suo complemento) che funziona per molti casi).

Quasi sempre, quando si cerca di fare il passo (1) per un problema indecidibile, è necessario il programma per controllare infinito numero di cose. Questo è di solito un segno che il problema non è decidibile.