Supongamos que hay una sesión de tutoría en una universidad. Tenemos un conjunto de k
Todos los estudiantes ingresan a la sesión de tutoría al principio (en t = 0
No he podido diseñar un algoritmo de tiempo polinómico ni probar la dureza N P.
Podemos definir una versión decisión del problema T T T = { ⟨ k , n , M Q , C ⟩ | ∃ sigma : T sigma ≤ C }
donde F Q es el conjunto de Q j 's.
Entonces podemos averiguar el mínimo
T sigma mediante la búsqueda binaria en C y averiguar la óptima σ utilizando las cesiones parciales de sigma en tiempo polinomial usando un oráculo para T T T . Además, T U T ∈ N P porque el σ óptimo se puede usar como un certificado que podemos verificar fácilmente en tiempo polinómico.
Mi pregunta: ¿ T U T N P -completo o podemos diseñar un algoritmo de tiempo polinómico para ello?
Nota al margen: Por cierto, pensé en esta pregunta después de una sesión de tutoría real, en la que el TA discutió las preguntas en el orden normal q 1 ... q n debido a que muchos estudiantes tuvieron que esperar hasta el final.
Ejemplo
Let k = 3 y n = 2 . Q 1 = { q 3 } y Q 2 = { q 1 , q 2 , q 3 } . Podemos ver que una óptima σ = ⟨ 3 , 1 , 2 ⟩ porque en ese caso, s 1 hojas después de t 1 = 1 y s 2 hojas después de t
∗ ¡ Eres libre de resolver el caso más general donde cada pregunta q i toma x i unidades para discutir!
fuente
Respuestas:
Sospecho que el problema T U T es NP-hard. Mostraré cómo transformar el problema de modo que esté fuertemente relacionado con un problema que es NP-hard. (Sí, todo esto es bastante vago. Básicamente creo que mi enfoque general es correcto, pero actualmente no puedo continuar).TUT
Primero, tenga en cuenta que el problema T U T puede reformularse de la siguiente manera:TUT
Dado un conjunto de preguntas Q de tamaño k , un conjunto de n subconjuntos F Q ⊆ P ( Q ) y un entero C , que hace existe una secuencia Σ : ⟨ S 1 , ... , S k ⟩ tal que, para todo i ∈ { 1 , ... , k } :Q k n FQ⊆P(Q) C Σ:⟨S1,…,Sk⟩ i∈{1,…,k}
Note that the set SiSi represent the first ii questions that will be explained. Conditions 1 and 2 ensure that the subsets are well formed according to this interpretation. Condition 3 counts the amount of students that haven't left at every moment in time, so it indeed sums up to the total waiting time among all students.
Now, we restrict the size of the subsets in FQFQ to 22 , so we can represent these subsets as edges on a graph where the vertices are the elements from QQ . (A hardness result for this special case is sufficient for hardness of the general problem)
Now, the problem of minimizing |{q∈FQ∣q⊈Si}||{q∈FQ∣q⊈Si}| for a single ii (this is essentially ignoring condition 2) is equivalent to the following problem, which I dub 'Double max k-vertex-coverDouble max k-vertex-cover ':
This problem is NP-hard, since kk -clique is a special case of this problem, as this answer shows. However, this is not sufficient to prove TUTTUT to be NP-hard, since we need to find the maximum for every ii , while respecting condition 2. This conditions are not satisfied by every sequence ΣΣ that satisfies only condition 1 and 3: consider the graph on 77 vertices with two disjoint cycles, one of size 44 , the other size 33 . For i=3i=3 , selecting all vertices in the 33 -cycle gives the maximum, while selecting all vertices of the 44 -cycle is optimal for i=4i=4 .
It seems that condition 2 makes the problem even harder and most certainly not easier, which means TUTTUT should be NP-hard, but I haven't seen a method to formally prove this.
So, to summarize, I have reduced the question to the following:
Side note: The formulation I gave makes it tempting to try an iterative algorithm which finds |{q∈FQ∣q⊈Si}||{q∈FQ∣q⊈Si}| under condition 2 from i=1…ki=1…k , by finding all maximum 'extenstions' of all found maximum sets for i−1i−1 . This does not lead to an efficient algorithm, as the amount of maximum sets at a single iteration may be exponential in k. Additionally, I have not seen a method to determine whether a subset for some i would eventually become the 'global' maximum to prevent checking an exponential amount of subsets.
fuente