On the Computational Complexity of Model Reconciliations
Authors: Sarath Sreedharan, Pascal Bercher, Subbarao Kambhampati
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we address this lacuna by introducing a decision-version of the model-reconciliation explanation generation problem and we show that it is ΣP 2 -complete. The proof will focus on mapping the explanation problem to that of establishing the satisfiability of a particular subclass of quantified boolean formulas. |
| Researcher Affiliation | Academia | Sarath Sreedharan1 , Pascal Bercher2 and Subbarao Kambhampati1 1School of Computing & AI, ASU 2The Australian National University sarath.sreedharan@colostate.edu, pascal.bercher@anu.edu.au, rao@asu.edu |
| Pseudocode | No | No structured pseudocode or algorithm blocks were found in the paper. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing open-source code for the methodology described. |
| Open Datasets | No | The paper describes theoretical work and does not use datasets for training or evaluation, therefore no information about public dataset availability is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve data splits for training, validation, or testing. |
| Hardware Specification | No | The paper describes theoretical work and does not report on experiments requiring hardware specifications. |
| Software Dependencies | No | The paper describes theoretical work and does not list specific software dependencies with version numbers for replication. |
| Experiment Setup | No | The paper describes theoretical work and does not provide details about an experimental setup, hyperparameters, or system-level training settings. |