Fråga (komplexitet)

I beskrivande komplexitet är en fråga en mappning från strukturer av en signatur till strukturer av en annan vokabulär. Neil Immerman , i sin bok Descriptive Complexity, "använder begreppet fråga som det grundläggande beräkningsparadigmet" (s. 17).

Givet signaturerna $\sigma$ och $\tau$ , definierar vi uppsättningen av strukturer på varje språk, ${\mbox{STRUC}}[\sigma ]$ och ${\mbox{STRUC}}[\tau ]$ . En fråga är då vilken mappning som helst

$I:{\mbox{STRUC}}[\sigma ]\to {\mbox{STRUC}}[\tau ]$

Beräkningskomplexitetsteori kan sedan formuleras i termer av kraften i den matematiska logik som är nödvändig för att uttrycka en given fråga.

Orderoberoende frågor

En fråga är ordningsoberoende om ordningen av objekt i strukturen inte påverkar resultatet av frågan. I databaser motsvarar dessa frågor generiska frågor (Immerman 1999, s. 18). En fråga är ordningsoberoende om $I({\mathfrak {A}})\equiv I({\mathfrak {B}})$ för alla isomorfa strukturer ${\mathfrak {A}}$ och ${\mathfrak {B}}$ .