Decidibilità dell'equivalenza alle formule esistenziali

Question

Sto cercando un algoritmo per decidere se una determinata formula del primo ordine su un vocabolario fisso ammette un esistenziale logicamente equivalente (cioè una formula in forma prenex in cui tutti i quantificatori sono esistenziali).

È noto se esiste un tale algoritmo o non esiste? Almeno quando non sono ammessi simboli di funzioni? E se esiste effettivamente, qual è la sua complessità?

So che, data una formula, possiamo costruirne una equivalente in forma prenex. Tuttavia, ecco un esempio che illustra che una formula, equivalente a una esistenziale, ammette anche una formula prenex equivalente che non è esistenziale:

Considera il vocabolario $ L = {e } $, dove $ E $ è un simbolo di relazione binaria. Quindi la formula$$ esiste x , e (x, x) $$che afferma che un grafico diretto ammette un ciclo, è una formula esistenziale ed è equivalente a$$ esiste x forall y , , , , x = y destra e (x, y) $$che è in forma prenex, ma non esistenziale. Quindi applicare l'algoritmo per costruire una forma prenex alla seconda formula non ne produrrebbe una esistenziale.