Ett svar på en fråga har en väldefinierad härstamning uttryck (alternativt kallas hur-bevisning) som förklarar hur svaret härleddes. Det senaste arbetet har också visat hur man beräknar ett icke-svars härstamning till en fråga. Orsaken till ett svar eller icke-svar är emellertid en mer subtil uppfattning och består i allmänhet endast av ett fragment av härstamningen. I detta dokument anpassar vi Halpern, Pearl och Chocklers senaste definitioner av kausalitet och ansvar för att definiera orsakerna till svar och icke-svar på frågor, och deras grad av ansvar. Ansvaret fångar uppfattningen om graden av orsakssamband och tjänar till att rangordna potentiellt många orsaker genom deras relativa bidrag till effekten. Sedan studerar vi komplexiteten i datorernas orsaker och ansvar för konjunktiva frågor. Det är känt att datororsakerna är NP-komplett i allmänhet. Vårt första huvudresultat visar att alla orsaker till konjunktiva frågor kan beräknas av en relationell fråga som kan innebära negation. Därför kan orsakssambandet beräknas i PTIME, och mycket effektivt så. Därefter studerar vi datoransvar. Här bevisar vi att komplexiteten beror på den konjunktiva frågan och visar en dikotomi mellan PTIME och NP-fullständiga fall. För PTIME-fallen ger vi en icke-trivial algoritm, som består av en minskning till maximalflödesberäkningsproblem. Slutligen bevisar vi att även när det är i PTIME är ansvaret fullständigt för LOGSPACE, vilket innebär att det, till skillnad från orsakssamband, inte kan beräknas genom en relationsfråga.
Meliou m.fl. REF beräknar orsaker till svar och icke-svar.
The Complexity of Causality and Responsibility for Query Answers and non-Answers
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}