On the Complexity of Trial and Error
Abstract
Motivated by certain applications from physics, biochemistry, economics, and computer science, in which the objects under investigation are not accessible because of various limitations, we propose a trial-and-error model to examine algorithmic issues in such situations. Given a search problem with a hidden input, we are asked to find a valid solution, to find which we can propose candidate solutions (trials), and use observed violations (errors), to prepare future proposals. In accordance with our motivating applications, we consider the fairly broad class of constraint satisfaction problems, and assume that errors are signaled by a verification oracle in the format of the index of a violated constraint (with the content of the constraint still hidden). Our discoveries are summarized as follows. On one hand, despite the seemingly very little information provided by the verification oracle, efficient algorithms do exist for a number of important problems. For the Nash, Core, Stable Matching, and SAT problems, the unknown-input versions are as hard as the corresponding known-input versions, up to a factor of polynomial. We further give almost tight bounds on the latter two problems' trial complexities. On the other hand, there are problems whose complexities are substantially increased in the unknown-input model. In particular, no time-efficient algorithms exist (under standard hardness assumptions) for Graph Isomorphism and Group Isomorphism problems. The tools used to…
Read the paper
Related studies
- Comparative effectiveness of GLP-1 receptor agonists on glycaemic control, body weight, and lipid profile for type 2 diabetes: systematic review and network meta-analysis
- Adverse effects of cyclooxygenase 2 inhibitors on renal and arrhythmia events: meta-analysis of randomized trials
- Benefits and harms of drug treatment for type 2 diabetes: systematic review and network meta-analysis of randomised controlled trials
- Comparative effectiveness and safety of statins as a class and of specific statins for primary prevention of cardiovascular disease: A systematic review, meta‐analysis, and network meta‐analysis of randomized trials with 94,283 participants
- Screen time increases overweight and obesity risk among adolescents: a systematic review and dose-response meta-analysis
- Exposure to WHO AWaRe antibiotics and isolation of multi-drug resistant bacteria: a systematic review and meta-analysis
Go deeper in Evidence Hub
Evidence Hub adds a study data sheet (design, sample size, evidence level, key numbers), an AI summary and a chat grounded in the paper's text.