Complexity of adaptive testing in scenarios defined extensionally  

作　　者：Ismael RODRÍGUEZ David RUBIO Fernando RUBIO 

机构地区：[1]Dpto.Sistemas Informáticos y Computación,Facultad de Informática,Universidad Complutense de Madrid,Madrid 28040,Spain [2]Instituto de Tecnologías del Conocimiento,Universidad Complutense de Madrid,Madrid 28040,Spain [3]Instituto de Biomecánica de Valencia.Universitat Politècnica de València,València 46022,Spain

出　　处：《Frontiers of Computer Science》2023年第3期11-28,共18页中国计算机科学前沿（英文版）

基　　金：This work has been partially supported by project PID2019-108528RB-C22;by Comunidad de Madrid as part of the program S2018/TCS-4339(BLOQUES-CM)co-funded by EIE Funds of the European Union.

摘　　要：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.

关 键 词：formal testing adaptive testing computational complexity PSPACE-completeness approximation hardness 

分 类 号：O17[理学—数学]