RT Journal Article
T1 Complexity of adaptive testing in scenarios defined extensionally
A1 Rodríguez Laguna, Ismael
A1 Rubio, David
A1 Rubio Díez, Fernando
AB 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 LogAPX-hardness are identified.
PB Springer
SN 2095-2236
YR 2022
FD 2022
LK https://hdl.handle.net/20.500.14352/88644
UL https://hdl.handle.net/20.500.14352/88644
LA eng
NO Rodríguez, I., Rubio, D. & Rubio, F. Complexity of adaptive testing in scenarios defined extensionally. Front. Comput. Sci. 17, 173206 (2023). https://doi.org/10.1007/s11704-022-1673-9
DS Docta Complutense
RD 26 mar 2026