Complexity of adaptive testing in scenarios defined extensionally
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909993387687936 |
|---|---|
| author | Rodriguez, Ismael Rubio, David Rubio, Fernando |
| author_facet | Rodriguez, Ismael Rubio, David Rubio, Fernando |
| contents | In this paper we consider a testing setting where the set of possible definitions of the Implementation Under Test (IUT), as well as the behavior of each of these definitions in all possible interactions, are extensionally defined, i.e., on an element-by-element and case-by-case basis. Under this setting, the problem of finding the minimum testing strategy such that collected observations will necessarily let us decide whether the IUT is correct or not (i.e., whether it necessarily belongs to the set of possible correct definitions or not) is studied in four possible problem variants: with or without non-determinism; and with or without more than one possible definition in the sets of possible correct and incorrect definitions. The computational complexity of these variants is studied, and properties such as PSPACE-completeness and Log-APX-hardness are identified. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_12056 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Complexity of adaptive testing in scenarios defined extensionally Rodriguez, Ismael Rubio, David Rubio, Fernando Computational Complexity In this paper we consider a testing setting where the set of possible definitions of the Implementation Under Test (IUT), as well as the behavior of each of these definitions in all possible interactions, are extensionally defined, i.e., on an element-by-element and case-by-case basis. Under this setting, the problem of finding the minimum testing strategy such that collected observations will necessarily let us decide whether the IUT is correct or not (i.e., whether it necessarily belongs to the set of possible correct definitions or not) is studied in four possible problem variants: with or without non-determinism; and with or without more than one possible definition in the sets of possible correct and incorrect definitions. The computational complexity of these variants is studied, and properties such as PSPACE-completeness and Log-APX-hardness are identified. |
| title | Complexity of adaptive testing in scenarios defined extensionally |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2601.12056 |