Complejidad del testing adaptativo en escenarios de testing definidos extensionalmente

Complejidad del testing adaptativo en escenarios de testing definidos extensionalmente Trabajo de Fin de Grado del Doble Grado en Ingeniería Informática y Matemáticas Alumno: David Rubio Ibáñez Director: Ismael Rodríguez Laguna 20 de septiembre de 2019 Tabla de contenidos Tabla de contenidos 1 Resumen 2 Introducción 3 Definiciones 5 Clasesdeproblemas ............................ 5 Testingadaptativo ............................. 6 Fórmula booleana cuantificada . . . . . . . . . . . . . . . . . . . . . . 8 Setcover .................................. 8 Demostraciones 10 N-ATESTesPSPACE........................... 10 N-ATESTkes PSPACE-completo . . . . . . . . . . . . . . . . . . . . . 12 “TQBF ⇒N-ATEST” ........................ 15 “N-ATEST ⇒TQBF” ........................ 17 ATEST con una única función correcta es log-APX . . . . . . . . . . . 21 ATESTeslog-APX-duro ......................... 22 Conclusiones 23 Apéndice 24 Bibliografía 25 1 Resumen 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. Aún 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. Palabras clave: testing adaptativo,complejidad computacional,PSPACEcompletitud,log-APX-completitud. 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. Key words: adaptive testing,computational complexity,PSPACE-completeness, log-APX-completeness. 2 Introducción En este trabajo estudiaremos la complejidad computacional del problema de testing adaptativo bajo ciertas condiciones. En el ámbito de testing queremos determinar si la implementación de un sistema cumple con ciertas especificaciones a base de interactuar con ella. Además, consideraremos que no podemos observar el funcionamiento interno de la implementación, es decir, que es una caja negra, por lo que lo único que podemos aprender sobre la implementación son los outputs que produce cuando introducimos ciertos inputs. Nosotros estudiaremos el testing adaptativo, en el que cada input introducido podrá depender de los outputs obtenidos previamente durante la aplicación de los inputs anteriores. En muchas circunstancias, esto puede acortar el número de interacciones necesarias para detectar errores. Los resultados que vamos a obtener aquí tratarán sobre un tipo de testing adaptativo muy determinado. Concretamente, habrá una cantidad finita de posibles comportamientos, correctos o no, que la implementación podrá tener y cada uno de estos posibles comportamientos nos será dado extensionalmente. Es decir, no se nos dará una regla o condición global que cumplan todas los sistemas posibles y otra regla o condición que cumplan todas las implementaciones correctas, si no que se nos listarán todas las posibles implementaciones y todas las implementaciones correctas una a una. Consideraremos que cada definición posible del comportamiento de una implementación para todos los inputs será dada por una función. Es más, la definición de cada una de estas funciones se nos dará extensionalmente: para cada input de un conjunto finito, nos dan el output que podrá devolver. Por tanto, no obtenemos el comportamiento a partir de una máquina abstracta (como una máquina finita de estados), si no como una simple lista finita de casos. Esta forma de representación, finita y nada compacta, es obviamente limitada. No obstante, es un caso especialmente útil desde el punto de vista teórico para obtener complejidades mínimas, pues la complejidad computacional que hallemos para este caso será la mínima complejidad para cualquier otro escenario de testing que lo generalice. Por ejemplo, si permitimos que la definiciones sean definidas usando ciertas máquinas, y se pueden codificar nuestras definiciones finitas extensionales usando dichas máquinas, entonces la complejidad del nuevo escenario será, al menos, la del caso puramente extensional. Aquí hay que tener en cuenta que las posibles definiciones de la implementación, tal y como nosotros las permitimos, no tienen en cuenta los inputs que se 3 les ha introducido anteriormente, como refleja el hecho de que hayamos escogido representarlas como funciones, donde obviamente cada aplicación de un input no afecta a posteriores aplicaciones. Esto puede ser una diferencia significativa con respecto a otros modelos de comportamiento como las máquinas de estados finitas o programas informáticos. Al testear modelos de cómputo que admiten estados internos tenemos que tener en cuenta que haciendo tests cambiamos el estado en el que estamos y, por tanto, también cambiamos el comportamiento que tendrá la máquina. Dado que volver al estado inicial puede no ser en absoluto trivial, nuestro modelo de testing parece sencillo en comparación, y sin embargo demostraremos para él un cierto nivel alto de complejidad mínima (PSPACE-dureza). Lo cual quiere decir que no es necesario ni tener distintos estados ni permitir infinitas formas posibles de interacción para alcanzar la PSPACE-dureza. El caso extensional también tiene utilidad práctica tal y como es. Con frecuencia, lo testeadores de software definen su plan de pruebas a mano y de manera extensional (definen, test a test, los posibles resultados correctos e incorrectos que se pueden obtener). Si cada prueba es muy costosa en tiempo o dinero, entonce elegir qué tests aplicar de entre los posibles tests es una tarea esencial. Dicho problema encaja, tal cual, en nuestra definición extensional de testing adaptativo. Aquí clasificaremos el testing adaptativo según las funciones (es decir, las posibles definiciones del comportamiento) puedan ser deterministas o no, y según pueda haber una o más funciones correctas. El caso determinista es un caso particular del no determinista, y el caso en el que solo hay una función correcta es un caso particular del caso en el que pueden haber varias. Cuando definamos extensionalmente funciones no deterministas, en vez de indicar el único output para cierto input, lo que se indicará será el conjunto de posibles outputs. La versión determinista de este problema se puede ver como el caso particular de la versión no determinista en el que todos los conjuntos contienen un único elemento. Las cotas superiores a la complejidad de un problema (como la pertenencia a cierta clase de complejidad) se pueden aplicar a los casos particulares de este, mientras que las cotas inferiores (como la la dureza o “hardness” con respecto a cierta clase) se pueden aplicar a las generalizaciones del problema en cuestión. Así, la cota superior a la complejidad que obtengamos del caso no determinista con múltiples funciones correctas nos servirá para todos los otros casos, y las cotas inferiores a la complejidad de los casos con una sola función correcta servirán para los casos con varias funciones correctas. 4 Definiciones Clases de problemas Los problemas computacionales se clasifican dependiendo del tiempo y espacio (memoria) máximos requeridos para resolver cualquier instancia. Cuando trabajemos con aproximaciones también se tendrá en cuenta la peor ratio de aproximación posible entre la solución obtenida y la correcta. El tiempo, espacio y ratio de aproximación de un problema se miden asintoticamente con respecto al tamaño de los datos de entrada[1]. En este trabajo hablaremos de dos clases: PSPACE: es la clase de los problemas resolubles en espacio polinómico[1]. Contiene todos los problemas resolubles en tiempo polinómico de forma determinista (P) o no determinista (NP)[2] porque, intuitivamente, no “les da tiempo” a usar más memoria. También contiene muchos problemas en los que hay que comprobar si todas las ramas de un árbol de decisiones de profundidad polinómica cumplen cierta propiedad independiente del resto de ramas, pues no hace falta guardar más de una rama simultaneamente. log-APX: es la clase de problemas para los que se puede conseguir en tiempo polinómico una solución aproximada con ratio de aproximación logarítmica con respecto al tamaño de entrada[3]. Llamamos reducción de un problema Aa otro B, y lo denotamos AB, a un procedimiento con el que transformar instancias del problema Aa instancias del problema Bque tengan el mismo resultado[4] o, en caso de estar usando aproximaciones, que mantengan cierta ratio de aproximación[5]. Intuitivamente, si ABes porque Bes tan o más difícil que A. Hay distintos tipos de reducciones atendiendo a cuánto tiempo y espacio necesitan o a cómo de buena es la aproximación. Una reducción que use más recursos computacionales que la solución directa del problema que queremos reducir no nos sirve, así que dependiendo de la clase de problemas con la que estemos tratando buscaremos reducciones más o menos costosas. Decimos que un problema es duro ohard con respecto a una clase si todos los problemas de esa clase se pueden reducir a él[6]. De nuevo, según la clase en cuestión permitiremos que la reducción consuma más o menos recursos computacionales. En el caso de nuestras demostraciones de dureza de PSPACE y log-APX podremos usar reducciones polinómicas en tiempo que, en el caso de log-APX, preserven el coste de todas las soluciones (no solo las óptimas, para así mantener la ratio de aproximación) [5][7]. 5 Los problemas duros con respecto a una clase que pertenecen a dicha clase se llaman completos ocomplete con respecto a esa clase[6]. Aquí lidiaremos con problemas de decisión que consisten en determinar si un elemento pertenece o no a cierto conjunto[7] y con problemas de optimización en los que hay que encontrar o el elemento de cierto conjunto con el mínimo coste o el mínimo coste para el que existe un elemento en dicho conjunto[2]. De los problemas de optimización se puede hacer una versión de decisión que determinen si la solución buscada tiene un coste menor que un número dado[2]. Testing adaptativo Dados dos conjuntos finitos no vacíos IyOque llamaremos conjuntos de inputs y outputs respectivamente diremos que un conjunto Cde funciones de I aOno deterministas es un formalismo computacional de IyO[8]: C⊆ {f:I→ P(O)\ {∅}} La finitud de IyOimplica la de C. Cada f∈Crepresenta el posible comportamiento de la caja negra que vamos a testear. Si toda f∈Ces determinista (∀i∈I f(i)unipuntual) diremos que Ces un formalismo computacional determinista, que será equivalente a definirlo como: C⊆ {f:I→O} Si Ces un formalismo computacional, llamaremos especificación a un subconjunto suyo E⊆Cy diremos que las funciones incluidas en la especificación f∈Eson “correctas” y el resto de funciones de Cno. En el problema de decisión de testing adaptativo intentaremos averiguar si, dados un formalismo computacional Cy una especificación E⊆C, se puede determinar con hasta ktests si cierta función, de la que solo conocemos los resultados de los tests, es “correcta” o no. Cada test consiste en proporcionar un input i∈Iy recibir un output o∈f(i)⊆O. Al ser testing adaptativo los inputs se pueden decidir en función de los resultados obtenidos en los test anteriores. Formalmente, dados dos conjuntos finitos no vacíos IyOdefinimos el pro6 blema de decisión de testing adaptativo no determinista como: N-ATEST := {(C, E, k) : E⊆C⊆ {f:I→ P(O)\ {∅}} , ∃i1∈I∀o1∈ ∪ f∈Cf(i1) ∃i2∈I∀o2∈ ∪ f∈{f∈C:o1∈f(i1)}f(i2) . . . ∃il∈I∀ol∈ ∪ f∈{f∈C:om∈f(im)∀m<l}f(il) . . . ∃ik∈I∀ok∈ ∪ f∈{f∈C:om∈f(im)∀m<k}f(ik) {f∈C:om∈f(im)∀m≤k} ⊆ E∨ {f∈C:om∈f(im)∀m≤k} ⊆ C\E} En esta definición los inputs dependen de los inputs y outputs anteriores. Los outputs han de ser consistentes con los inputs y outputs anteriores, es decir, tiene que existir una función en Cque pueda dar esos resultados. Las funciones consistentes con todos los inputs y outputs ({f∈C:om∈f(im)∀m≤k}) han de ser todas correctas (⊆E) o todas incorrectas (⊆C\E). Interesa considerar aparte el caso en el que el formalismo computacional es determinista. Así, dados dos conjuntos finitos no vacíos IyOdefinimos el problema de decisión de testing adaptativo determinista como: ATEST := {(C, E, k) : E⊆C⊆ {f:I→O} ∃i1∈I∀o1∈ {f(i1) : f∈C} ∃i2∈I∀o2∈ {f(i2) : f∈C, o1=f(i1)} . . . ∃il∈I∀ol∈ {f(il) : f∈C, om=f(im)∀m<l} . . . ∃ik∈I∀ok∈ {f(ik) : f∈C, om=f(im)∀m<k} {f∈C:om=f(im)∀m≤k} ⊆ E∨ {f∈C:om=f(im)∀m≤k} ⊆ C\E} Definiremos la versión de optimización del problema de testing adaptativo determinista como: m´ın{k: (C, E, k)∈ATEST} 7 A continuación definiremos los problemas TQBF y SET-COVER que son los que reduciremos a N-ATEST y ATEST respectivamente para determinar su complejidad. Fórmula booleana cuantificada En el problema de la fórmula booleana cuantificada o True Quantified Boolean Formulae (TQBF) queremos determinar si una fórmula booleana con las variables cuantificadas con paratodos yexistes es satisfactible[6]. Hay distintos enunciados de este problema que permiten que la fórmula esté de cualquier forma, que esté en forma normal conjuntiva o CNF (por sus siglas en inglés), que esté en forma normal disyuntiva o DNF, que esté en 3CNF o que esté en 3DNF[1][6]. Todas estas formas son equivalentes pues se pueden transformar unas en otras en tiempo polinómico manteniendo la satisfacibilidad, tal y como comentamos en el apéndice. Nosotros exigiremos que la fórmula esté en CNF. También obligaremos a que los existes y los paratodos se alternen y no estén negados. Nuevamente, las fórmulas que no cumplan con esto pueden ser transformadas a otras que sí en tiempo polinómico. Con todo esto la definición formal queda: TQBF := {φ(x1, y1, x2, y2, . . . , xk, yk) : φes CNF y ∃x1∀y1∃x2∀y2. . . ∃xk∀ykφ(x1, y1, x2, y2, . . . , xk, yk)=1} Es importante que las variables tengan un orden establecido al ser cuantificadas, pues cambiar el orden de la cuantificación de variables para una misma fórmula puede hacer que el resultado de TQBF cambie. Como por ejemplo en este caso: ∃x1∀y1∃x2∀y2(x2∧y1)∨(x2∧y1)∃x2∀y2∃x1∀y1(x2∧y1)∨(x2∧y1) la primera instancia de TQBF es cierta tomando x2=y1pero la segunda no, pues cuando y1=x2la fórmula no se cumplirá. TQBF es PSPACE-completo[6]. Set cover En el problema de decisión de SET-COVER queremos saber si, dado un conjunto finito y un recubrimiento {Sl}m l=1 de este, existe un subrecubrimiento de como mucho ksubconjuntos: SET-COVER ={({Sl}m l=1, k) : ∃{Slj}k j=1 ⊆ {Sl}m l=1, k [ j=1 Slj= m [ l=1 Sl} 8 fl(xj) = f0 l(x0 j) = {0,1}para j6=l, l + 1, es decir, el resto de casos. Las funciones flyf0 lse comportan igual con una variable que con su negada: fl(xj) = fl(xj)fl(x0 j) = fl(x0 j) f0 l(xj) = f0 l(xj)f0 l(x0 j) = f0 l(x0 j) Para que alguna de x1, x1, x0 1, x0 1descarte dos funciones tenemos que crear una función adicional que solo sea descartada por alguno de estos inputs: f0(x1) = f0(x1) = f0(x0 1) = f0(x0 1) = {−2} f0(xj) = f0(xj) = f0(x0 j) = f0(x0 j) = {0,1}para 1< j ≤k Y hasta aquí la transformación necesaria. A continuación demostraremos que la instancia de TQBF se cumple si y solo si la instancia de N-ATEST que hemos creado a partir de ella también se cumple. Nótese que esta transformación se puede hacer en tiempo polinómico con respecto al tamaño de φpues el número de funciones es del orden del número de cláusulas más el número variables y cada una acepta una cantidad de inputs del orden del número de variables. “TQBF ⇒N-ATEST” Veamos que si la fórmula booleana cuantificada se cumple entonces la instancia correspondiente de testing adaptativo también: φ(x1, . . . , yk)∈TQBF ⇒(C, E, k)∈N-ATEST Primero veamos que descartaremos todas las flsi ponemos los xj,xj, x0 j, x0 j en orden y elegimos bien entre las versiones prima y no prima. Es decir, si i1∈ {x1, x1, x0 1, x0 1} y para 1≤l < k: si ol<0entonces il+1 ∈ {xl+1, xl+1, x0 l+1, x0 l+1} si ol= 0 entonces il+1 ∈ {x0 l+1, x0 l+1} si ol= 1 entonces il+1 ∈ {xl+1, xl+1} 15 entonces o bien algún output es negativo y todas las funciones consistentes con los inputs y outputs son incorrectas: {f∈C:om∈f(im), m ≤k} ⊆ C\Ey∃oM<0 o bien todos los outputs son positivos y las funciones fl,f0 lyf0son descartadas: ∀l fl, f0 l, f0/∈ {f∈C:om∈f(im), m ≤k}y ∃oM<0 Si ∃oM<0entonces todas las funciones consistentes con los inputs y outputs son incorrectas: {f∈C:om∈f(im), i ≤k}⊆{f∈C: 0 > oM∈f(iM)} ⊆ C\E pues la única función correcta g(E={g}) solo tiene como outputs 0y1. Si  ∃oM<0entonces para todo 1≤l < k: ol= 0 ⇒(0 = ol/∈f0 l(il) = {1} il+1 ∈ {x0 l+1, x0 l+1} ⇒ 0≤ol+1 /∈fl(il+1) = {−2} ol= 1 ⇒(1 = ol/∈fl(il) = {0} il+1 ∈ {xl+1, xl+1} ⇒ 0≤ol+1 /∈f0 l(il+1) = {−2} Y como i1∈ {x1, x1, x0 1, x0 1}entonces 0≤o1/∈f0(i1) = {−2}. Así que fl, f0 l, f0/∈ {f∈C:om∈f(im), m ≤k}. Veamos ahora que si la fórmula booleana cuantificada se cumple entonces podemos descartar todas las fci. Es decir que si ∃x1∀y1. . . ∃xk∀ykφ(x1, y1, x2, y2, . . . , xk, yk)=1 y si x1= 1 para la fórmula entonces tomamos i1∈ {x1, x0 1} si x1= 0 entonces tomamos i1∈ {x1, x0 1} y para 1≤l < k: si ol<0entonces il+1 ∈ {xl+1, xl+1, x0 l+1, x0 l+1} si no, tomando yl=ol, elegimos (il+1 ∈ {xl+1, x0 l+1}si xl+1 = 1 il+1 ∈ {xl+1, x0 l+1}si xl+1 = 0 entonces o bien algún output es negativo y todas las funciones consistentes con los inputs y outputs son incorrectas {f∈C:om∈f(im), m ≤k} ⊆ C\Ey∃oM<0 o bien todos los outputs son positivos y las funciones fcison descartadas: ∀i fci/∈ {f∈C:om∈f(im), m ≤k}y ∃oM<0 16 Nótese que esta elección de iles compatible con la elección que hemos hecho para descartar las funciones fl,f0 lyf0(en la que elegíamos entre las versiones con y sin prima) y que el resultado también es compatible. Si ∃oM<0entonces todas las funciones consistentes con los inputs y outputs son incorrectas: {f∈C:om∈f(im), i ≤k}⊆{f∈C: 0 > oM∈f(iM)} ⊆ C\E pues la única función correcta g(E={g}) solo tiene como outputs 0y1. Si  ∃oM<0entonce para todo 1≤i≤N(número de cláusulas de φ) y para cualquier 1≤j≤k: si xj= 1 (entonces ij∈ {xj, x0 j}) y xj∈ci⇒0≤oj/∈fci(ij) = {−1}. si xj= 0 (entonces ij∈ {xj, x0 j}) y xj∈ci⇒0≤oj/∈fci(ij) = {−1}. si yj, yj∈cicomo ij∈ {xj, xj, x0 j, x0 j}entonces 0≤oj/∈fci(ij) = {−1}. si yj∈cipero yj/∈ciyyj= 1 entonces fci(ij)vale {0}o{−1}para ij∈ {xj, xj, x0 j, x0 j}y1 = yj=oj/∈fci(ij)⊂ {−1,0}. si yj∈cipero yj/∈ciyyj= 0 entonces fci(ij)vale {1}o{−1}para ij∈ {xj, xj, x0 j, x0 j}y0 = yj=oj/∈fci(il)⊂ {−1,1}. En definitiva, si cise cumple (tiene algún literal con valor 1) entonces fci/∈ {f∈C:om∈f(im), m ≤k}. Luego si φ(x1, . . . , yk)se cumple entonces ninguna fciestá en {f∈C:om∈f(im), m ≤k}. Combinando ambos argumentos: si introducimos las variables en orden y φ se cumple entonces podemos descartar o go el resto de funciones (fci, fl, f0) y por tanto (C, E)∈N-ATESTk. “N-ATEST ⇒TQBF” Veamos ahora que la fórmula booleana cuantificada se cumple si la instancia correspondiente de testing adaptativo también: φ(x1, . . . , yk)∈TQBF ⇐(C, E, k)∈N-ATEST Primero demostraremos que para que (C, E, k)∈N-ATEST es necesario usar al menos un input de entre xj, xj, x0 j, x0 jpara cada 1≤j≤ky, por tanto, como solo podemos usar kinputs entonces tenemos que usar un y solo un literal por cada j. Es decir: (C, E, k)∈N-ATEST ⇒ ∃j:xj, xj, x0 j, x0 j/∈ {im}k m=1 17 Supongamos que (C, E, k)∈N-ATEST y tomemos una elección de inputs {im}k m=1 con sus correspondientes outputs {om}k m=1. Si existe om<0entonces {f∈C:om∈f(im), i ≤k} ⊆ C\E, pues E={g} ygsolo devuelve 0o1. Consideremos ahora solo el otro caso: om∈ {0,1}para todo 1≤m≤k. En este caso tenemos que g∈ {f∈C:om∈f(im), i ≤k}y como (C, E, k)∈ N-ATEST entonces E={g}={f∈C:om∈f(im), i ≤k}. Veamos que esto no es cierto si ∃j:xj, xj, x0 j, x0 j/∈ {im}k m=1: Si j= 1 entonces f0no se podría distinguir de gcon ningún input. Es decir, f0∈ {f∈C:om∈f(im), i ≤k}lo cual es contradictorio. Si j > 1y ∃in∈ {xj−1, xj−1, x0 j−1, x0 j−1}entonces para todo mtendríamos que fj−1(im) = f0 j−1(im) = {0,1}y por tanto fj−1, f0 j−1∈ {f∈C:om∈f(im), i ≤k}contradiciendo nuestra premisa. Si j > 1y∃!iM∈ {xj−1, xj−1, x0 j−1, x0 j−1}entonces si oM= 0 fj−1∈ {f∈C:om∈f(im), i ≤k}, pues solo las variables xj, xj, x0 j, x0 jpodrían distinguir fj−1de g, y análogamente su oM= 1 entonces tendríamos f0 j−1∈ {f∈C:om∈f(im), i ≤k}. Si j > 1y∃iM1, iM2, . . . , iMp∈ {xj−1, xj−1, x0 j−1, x0 j−1}entonces en el caso en que oM1=oM2=. . . =oMpno podríamos descartar fj−1por el razonamiento anterior así que esa elección de iMno es válida. Ahora demostraremos que hay que introducir las variables por orden. Es decir: (C, E, k)∈N-ATEST ⇒ ∀j:ij∈ {xj, xj, x0 j, x0 j} Supongamos que (C, E, k)∈N-ATEST y tomemos una elección de inputs {im}k m=1 con sus correspondientes outputs {om}k m=1 tales que las funciones en Cconsistentes con esos outputs sean todas “correctas” o todas “incorrectas”. En caso de que exista om<0tendremos que {f∈C:om∈f(im), i ≤k} ⊆ C\E, pues E={g}ygsolo devuelve 0o1. Así que tendremos que buscar la contradicción en los restantes casos: om∈ {0,1}para todo 1≤m≤ky 18 por tanto g∈ {f∈C:om∈f(im), i ≤k}. Para que (C, E, k)∈N-ATEST hace falta que en estos casos E={g}={f∈C:om∈f(im), i ≤k}. Razonemos por reducción al absurdo y tomemos el menor jtal que ij/∈ {xj, xj, x0 j, x0 j}. Tendremos entonces que ij∈ {xn, xn, x0 n, x0 n}para algún n>j. Llamemos il∈ {xn−1, xn−1, x0 n−1, x0 n−1}y tendremos que l > j (de lo contrario l=n−1lo cual entra en contradicción con que ijsea el primer input desordenado). Entonces si ij∈ {xn, xn}(respectivamente ij∈ {x0 n, x0 n}), cuando oj∈ {0,1}tendremos que fn−1(respectivamente f0 n−1)∈ {f∈C:om∈f(im), i ≤j} y en los casos en los que ol= 0 (respectivamente ol= 1) tendremos que fn−1(respectivamente f0 n−1)∈ {f∈C:om∈f(im), i ≤k}, pues solo usando las variables con subíndices nyn−1se puede distinguir estas funciones de g. Demostraremos ahora que si (C, E, k)∈N-ATEST entonces φ(x1, . . . , yk)∈ TQBF sabiendo ya que ij∈ {xj, xj, x0 j, x0 j}. Para resolver φtomaremos: xj= 1 si ij∈ {xj, x0 j} xj= 0 si ij∈ {xj, x0 j} Los valores de ij, con j > 1, vendrán dados por los valores anteriores de oj−1 que tomaremos como oj−1=yj−1. Como oj=yjestamos en los casos en que om∈ {0,1}para todo 1≤m≤k, luego g∈ {f∈C:om∈f(im), i ≤k}y, para que (C, E, k)∈N-ATEST, tendrá que ser E={g}={f∈C:om∈f(im), i ≤k}. Veamos que si fcise ha descartado (fci/∈ {f∈C:om∈f(im), i ≤k}) entonces cise cumple. Para descartar fcitiene que existir iMtal que oM/∈fci(iM). Esto se dará, para empezar, en los casos en que f(iM) = {−1}que son: xM∈ci,iM∈ {xM, x0 M}y, por tanto, xM= 1. xM∈ci,iv∈ {xv, x0 M}y, por tanto, xM= 0. yM, yM∈ci. En todos estos casos ci= 1, es decir, se cumple. En el resto de casos se dará: 19 si yM∈cipero xM, yM/∈cientonces fci(iM) = {0}para iM∈ {xM, x0 M} y por tanto fciserá distinguible si oM= 1. si yM∈cipero xM, yM/∈cientonces fci(iM) = {0}para iM∈ {xM, x0 M} y por tanto fciserá distinguible si oM= 1. si yM∈cipero xM, yM/∈cientonces fci(iM) = {1}para iM∈ {xM, x0 M} y por tanto fciserá distinguible si oM= 0. si yM∈cipero xM, yM/∈cientonces fci(iM) = {1}para iM∈ {xM, x0 M} y por tanto fciserá distinguible si oM= 0. Es decir que si fcies distinguible entonces yM∈ciyoM=yM= 1 oyM∈ci yoM=yM= 0. En ambos casos ci= 1. Ya no hay más casos en los que fcisea distinguible porque en el resto de casos fci(iM) = {0,1}. Como todos los cise cumplen entonces φse cumple. 20 ATEST con una única función correcta es log-APX Reduciremos el problema de optimización ATEST con una única función correcta a el problema de optimización SET-COVER que está en log-APX. Hemos definido estos problemas de optimización como: m´ın{k: ({Sl}m l=1, k)∈SET-COVER} y m´ın{k: (C, E, k)∈ATEST} Luego si conseguimos reducir el problema de decisión de ATEST al de SETCOVER de forma que todas las soluciones que obtengamos (no solo las correspondientes a las óptimas del problema de optimización) en SET-COVER se traduzcan a soluciones de ATEST con exactamente el mismo coste k, entonces tendremos que el resultado del problema de optimización (incluso con aproximaciones) es exactamente el mismo. Esta reducción, evidentemente, preserva la ratio de aproximación (pues tanto la solución optima como las aproximadas son exactamente iguales). A este tipo de reducción se le conoce como S-reducción, que es la más fuerte de una serie de tipos de reducciones que propagan la pertenencia y dureza en log-APX[5]. Para reducir un problema de decisión a otro tenemos que ver que: (C, {h}, k)∈ATEST ⇔({Si}i∈I, k)∈SET-COVER donde S i∈I Si=C\{h}yf∈Si, con i∈I, si f(i)6=h(i). Si ({Si}i∈I, k)∈SET-COVER es porque existe J⊆Icon |J| ≤ ktal que S i∈I Si=C\{h}=S j∈J Sjentonces para todo f∈C\{h}existe j∈Jtal que f∈Sjo, lo que es lo mismo, f(j)6=h(j). Tomando entonces los elementos de Jcomo inputs en ATESTktenemos que si algún output es distinto de lo que respondería hentonces hemos descartado h, si no hemos descartado todas las demás porque para cualquier f∈C\{h}algún j∈Jhace que f(j)6=h(j). Recíprocamente, si (C, {h}, k)∈ATEST y elegimos los conjuntos Sjde las jque usamos como inputs en el caso en que todos los outputs sean consistentes con hentonces como todas las funciones en C\{h}han sido descartadas es porque f(j)6=h(j)⇔f∈Sj, para algún jde los inputs usados. Con esto no solo podemos decir que la versión de optimización de ATEST es log-APX, también podemos decir que la versión de decisión de ATEST es NP como SET-COVER. 21 ATEST es log-APX-duro Demostraremos ahora que el problema de optimización SET-COVER se puede reducir al problema de optimización ATEST que es log-APX-duro. Igual que antes, para demostrar la reducción entre las versiones de optimización nos basta con reducir las versiones de decisión manteniendo la misma k, es decir: ({Sl}m l=1, k)∈SET-COVER ⇔(C, {h}, k)∈ATEST donde I={1,2, . . . , m},O={0,1},h≡0,C={h, fecon e∈S1≤l≤mSl} yfe(l)=1si e∈Sl,fe(l)=0si e /∈Sl. Es decir, los conjuntos son inputs y sus elementos son funciones que devuelven 1o0según el elemento esté en el conjunto input o no. Si ({Sl}m l=1, k)∈SET-COVER es porque ∃{Slj}k j=1 ⊂ {Sl}m l=1 que cumple SSl=SSljy entonces para todo e∈SSlexiste SlMtal que e∈SlMy por tanto fe(lM) = 1. Es decir que si tomamos los inputs como ij=ljtodas las funciones fedevolverán 1para algún input, luego podrán ser distinguidas de la función h, que es idénticamente nula. O más formalmente: si existe oM= 1 entonces h /∈ {f∈C:oM= 1 = f(iM)} ⊆ {f∈C:om=f(im), m ≤k} ⊆ C\Ey si om= 0 para todo 1≤m≤kentonces para cualquier e∈SSl, fe/∈ {f∈C:om= 0 = f(im), m ≤k}pues como hemos visto existe iM=lM tal que fe(iM)=1y por tanto {f∈C:om=f(im), m ≤k} ⊆ E={h}. Recíprocamente si (C, E, k)∈ATEST tomaremos lj=ijcon om= 0 para 1≤m≤k, lo cual es posible porque h≡0. Con estos inputs y outputs sabemos que {f∈C:om=f(im), m ≤k}=E={h}porque (C, E, k)∈ATEST. Luego para todo e∈SSlexiste lM=iMtal que fe(iM) = 1 y por tanto e∈SlM. Así que SSl=SSlj. Esta también es una S-reducción: las soluciones de uno y otro problema tienen exactamente el mismo coste[5]. Con esto no solo podemos decir que la versión de optimización de ATEST es log-APX-duro, también podemos decir que la versión de decisión de ATEST es NP-duro como SET-COVER. 22 Conclusiones Como ya adelantábamos en la introducción, hemos determinado la complejidad computacional distintas versiones del testing adaptativo (salvo la versión determinista con múltiples funciones correctas, para la que no hemos encontrado resultado de completitud, aunque sí dureza). La siguiente tabla resume los resultados obtenidos: Una función correcta Múltiples funciones correctas No determinista PSPACE-completo Determinista log-APX-completo (optimización) NP-completo (decisión) log-APX-duro (optimización) PSPACE, NP-duro (decisión) Determinar la complejidad exacta del caso determinista con múltiples funciones correctas queda como trabajo futuro. As we already discuss in the introduction, we’ve determined the computational complexity of different variants of the adaptive testing (except the deterministic version with multiple correct functions, for which we haven’t found a completeness result, but just a harndness one). The next table summarizes the obtained results: One correct function Multiple correct functions No deterministic PSPACE-complete Deterministic log-APX-complete (optimization) NP-complete (decision) log-APX-hard (optimization) PSPACE, NP-hard (decision) Determining the exact complexity of the deterministic case with multiple correct functions is left as future work. 23 Apéndice Comentaremos brevemente como transformar una fórmula cuantificada cualquiera en una en la que los cuantificadores estén alternados y la expresión booleana esté en forma normal conjuntiva (el caso de la forma normal disyuntiva es análogo). Primero quitaremos los cuantificadores negados usando las siguientes equivalencias:  ∃x ψ(x)⇔ ∀x¬ψ(x) ∀x ψ(x)⇔ ∃x¬ψ(x) donde ψpuede contener más cuantificadores y la negación se aplicaría al primero de ellos. Para que los existes y para todos se alternen, basta con crear variables auxiliares que no se usen. Esto hace que las fórmulas no sean equivalentes, pues una tiene más variables que la otra, pero sí se mantiene la satisfacibilidad. Para convertir la fórmula booleana a CNF primero tenemos que quedarnos solo con variables y operaciones básicas: conjunciones, disyunciones y negaciones. Las implicaciones, disyunciones exclusivas y equivalencias hay que expresarlas en términos de operaciones básicas. A continuación hay que usar las leyes de De Morgan y la doble negación para que las negaciones solo se apliquen a variables. El último paso es el que más problemas da, pues consiste en cambiar disyunciones por conjunciones y viceversa usando la ley distributiva. Esto puede causar que la nueva fórmula tenga un tamaño exponencial comparado con la fórmula original. En lugar de esto, lo que habrá que hacer es introducir nuevas variables. Lo que haremos para transformar una disyunción en una conjunción será, por cada cláusula conjuntiva original, crear una variable cuantificada con un existe. Todas las nuevas variables se pondrán en una disyunción (así que al menos una tendrá que ser cierta), y por cada literal original y cada claúsula conjuntiva original en la que estuviese se crea una disyunción que contiene el literal con la nueva variable (asociada a la cláusula en la que estaba el literal) negada. Así, como al menos una variable nueva tendrá que ser cierta, obligará a que se cumplan todos los literales que estaban en la cláusula a la que está asociada dicha nueva variable[7][12]. Para convertir una fórmula de CNF a 3CNF hay que dividir sucesivamente las disyunciones en dos hasta que ninguna tenga más de 3 variables. Para cada división creamos una nueva variable, dos de las variables originales se ponen en disyunción con la nueva variable, el resto de variables se ponen con la nueva variable pero negada. Una de estas disyunciones será cierta gracias a la nueva variable, la otra tendrá que hacerse cierta por una de las variables originales. 24