Complejidad del testing adaptativo en escenarios de testing definidos extensionalmente

Abstract

Introducimos el concepto de testing adaptativo definido extensionalmente con sus distintas variantes (hay determinismo o no, hay una única definición correcta de implementación o no) y demostramos cotas superiores de su complejidad para todos los casos (PSPACE) y para el caso determinista en el que solo hay una posible definición correcta de implementación (log-APX), así como cotas inferiores tanto para el caso no determinista (PSPACE-dureza) como para el caso determinista (log-APX-dureza). El hecho de que haya que hacer las definiciones extensionalmente quiere decir que este tipo de testing adaptativo es relativamente sencillo. Aun así obtenemos un nivel relativamente alto de complejidad, lo cual quiere decir que los tipos de testing adaptativos que generalicen a este tendrán también un nivel alto de complejidad.We introduce the concept of adaptive testing defined extensionally with different variants (determinism or not, there’s only one correct implementation or not) and we prove upper bounds of its complexity for all the cases (PSPACE) and the variant with determinism and only one correct implementation (log-APX), as well as lower bounds to the non-deterministic variant (PSPACEhardness) and for the deterministic variant (log-APX-hardness). Having extensional definitions means that this type of adaptive testing is relatively simple. Even so, we get a high complexity level, which means that the types of adaptive testing that generalize this one will also have a high complexity level.