Caratterizzazione logica del problema P rispetto a NP (e riferimenti per la logica del punto meno fisso)
-
05-11-2019 - |
Domanda
Wikipedia dice che segue (e altro) sulla caratterizzazione logica del problema P rispetto a NP qui:
Pertanto, la domanda "è un sottoinsieme adeguato di NP" può essere riformulata in quanto "è una logica di secondo ordine esistenziale in grado di descrivere le lingue (di strutture limitate limitate con firma non banale) che la logica del primo ordine con minimo punto fisso non può?"
La mia domanda è: è stato fatto qualche lavoro per affrontare il problema P rispetto a NP da questo angolo logico, ragionando la logica esistenziale del secondo ordine e la logica del primo ordine con il minimo punto?
E più in generale, quali sono alcuni buoni riferimenti per conoscere la logica dei punti meno fissi?
Nessuna soluzione corretta
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange