Encontrar a sequência ideal de perguntas para minimizar o tempo total do aluno

Suponha que exista uma sessão de tutorial em uma universidade. Temos um conjunto de perguntas e um conjunto de alunos . Cada aluno tem uma dúvida em um determinado subconjunto de perguntas, ou seja, para cada aluno , seja o conjunto de perguntas que um aluno duvida. Assume-se que e .$k$$Q = \{ q_1 \ldots q_k \}$$n$$S = \{ s_1 \ldots s_n \}$$s_j$$Q_j \subseteq Q$$\forall 1 \leq j \leq n: Q_j \neq \phi$$\bigcup_{1\leq j\leq n}Q_j = Q$

Todos os alunos entram na sessão do tutorial no início (em ). Agora, um aluno sai da sessão do tutorial assim que todas as perguntas em que ele tiver dúvidas tiverem sido discutidas. Suponha que o tempo necessário para discutir cada questão seja igual, digamos 1 unidade . Seja o tempo gasto por na sessão do tutorial. Queremos encontrar uma permutação ideal na qual questões são discutidas como a quantidade é minimizado.∗ t j s j σ ( q σ ( 1 ) … q σ ( n ) ) T σ = Σ 1 ≤ j ≤ n t $t = 0$$^*$$t_j$$s_j$$\sigma$$(q_{\sigma(1)} \ldots q_{\sigma(n)})$$T_\sigma = \Sigma_{1\leq j \leq n}t_j$

Não pude projetar um algoritmo de tempo polinomial ou provar a dureza $\mathsf{NP}$ .

Podemos definir uma versão de decisão do problema

onde $\mathcal{F}_Q$ é o conjunto de $Q_j$ 's.

Podemos então descobrir o T_ \ sigma mínimo $T_\sigma$usando pesquisa binária em $C$ e descobrir o \ sigma ideal $\sigma$usando atribuições parciais a $\sigma$ em tempo polinomial usando um oracle para $\mathsf{TUT}$ . Além disso, $\mathsf{TUT} \in \mathsf{NP}$ porque o \ sigma ideal $\sigma$pode ser usado como um certificado que podemos verificar facilmente em tempo polinomial.

Minha pergunta: concluída ou podemos criar um algoritmo de tempo polinomial para ele?N $\mathsf{TUT}$ $\mathsf{NP}$

Sidenote: A propósito, pensei nessa questão após uma sessão de tutorial real, na qual o AT discutiu as questões na ordem normal por causa da qual muitos estudantes tiveram que esperar até o final.$q_1 \ldots q_n$

Exemplo
Let e . e . Podemos ver que ideal porque, nesse caso, sai depois de e sai depois de , então a soma é 4. No entanto, se discutirmos as questões em a ordem , então e precisam esperar até o fim e , então a soma é 6.$k=3$$n=2$$Q_1 = \{q_3\}$$Q_2 = \{q_1, q_2, q_3\}$$\sigma = \langle 3, 1, 2 \rangle$$s_1$$t_1 = 1$$s_2$$t_2 = 3$
$\langle 1, 2, 3\rangle$$s_1$$s_2$$t_1 = t_2 = 3$

Q i x $^*$ Você é livre para resolver o caso mais geral em que cada pergunta leva unidades para discutir!$q_i$$x_i$

Suspeito que o problema seja NP-difícil. Vou mostrar como transformar o problema de forma que ele esteja fortemente relacionado a um problema que é difícil para o NP. (Sim, tudo isso é bastante vago. Basicamente, acho que minha abordagem geral está correta, mas atualmente não consigo prosseguir.)$\mathsf{TUT}$

Primeiro, observe que o problema pode ser reformulado da seguinte maneira:$\mathsf{TUT}$

Dado um conjunto de perguntas de tamanho k , um conjunto de n subconjuntos F Q ⊆ P ( Q ) e um número inteiro C , não existe uma sequência Σ : ⟨ S 1 , ... , S k ⟩ de tal modo que, para todos os i ∈ { 1 , … , k } :$Q$$k$$n$$\mathcal{F}_Q\subseteq \mathcal{P}(Q)$$C$$\Sigma : \langle S_1,\ldots, S_k\rangle$$i \in\{1,\ldots,k\}$

1. e | S i | = i ; e$S_i\subseteq Q$$|S_i|=i$
2. para todos os j > i ; e$S_i \subset S_j$$j>i$
3. ?$\sum_{i=1}^k |\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}| \leq C$

Observe que o conjunto representa as primeiras i perguntas que serão explicadas. As condições 1 e 2 garantem que os subconjuntos sejam bem formados de acordo com esta interpretação. A condição 3 conta a quantidade de estudantes que não saíram a todo momento, portanto, isso realmente resume o tempo total de espera entre todos os alunos.$S_i$$i$

Agora, podemos restringir o tamanho dos subconjuntos em a 2 , de modo que pode representar estes subconjuntos como arestas em um gráfico onde os vértices são os elementos de Q . (Um resultado de dureza para este caso especial é suficiente para a dureza do problema geral)$\mathcal{F}_Q$$2$$Q$

Agora, o problema de minimizar para um único i (essa é essencialmente a condição 2 de ignorar) é equivalente ao seguinte problema, que eu chamo de ' Double max  k -vertex-cover ':$|\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}|$$i$$\mathsf{\text{Double max $k$-vertex-cover}}$

Dado um gráfico não direcionado e números inteiros k e t , existe um conjunto de vértices V ′ ⊆ V de tamanho no máximo k de modo que o conjunto { ( u , v ) ∈ E ∣ u ∈ V ′ ∧ v ∈ V ′ } tem um tamanho de pelo menos t ?$G=(V,E)$$k$$t$$V'\subseteq V$$k$$\{(u,v)\in E\mid u\in V' \wedge v \in V' \}$$t$

Esse problema é difícil para o NP, pois o -clique é um caso especial desse problema, como mostra a resposta . No entanto, isso não é suficiente para provar que T U T é NP-difícil, pois precisamos encontrar o máximo para cada i , respeitando a condição 2. Essas condições não são satisfeitas por todas as seqüências Σ que satisfazem apenas as condições 1 e 3: considere o gráfico em 7 vértices com dois ciclos disjuntos, um de tamanho 4 e outro de tamanho 3 . Para i = 3 , selecionar todos os vértices do ciclo 3 fornece o máximo, enquanto selecionar todos os vértices dos $k$$\mathsf{TUT}$$i$$\Sigma$$7$$4$$3$$i=3$$3$$4$-ciclo é ideal para .$i=4$

Parece que a condição 2 torna o problema ainda mais difícil e certamente não é mais fácil, o que significa que deve ser NP-difícil, mas eu não vi um método para provar isso formalmente.$\mathsf{TUT}$

Então, para resumir, reduzi a pergunta para o seguinte:

• É possível incluir a condição 2 para concluir a prova de dureza para ?$\mathsf{TUT}$

Nota lateral: A formulação que eu dei torna tentador tentar um algoritmo iterativo que encontre na condição 2 de i = 1 … k , encontrando todas as 'extensões' máximas de todos os conjuntos máximos encontrados para i - 1 . Isso não leva a um algoritmo eficiente, pois a quantidade de conjuntos máximos em uma única iteração pode ser exponencial em k . Além disso, eu não vi um método para determinar se um subconjunto para alguns $|\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}|$$i=1\ldots k$$i-1$$k$$i$ acabaria por se tornar o máximo "global" para impedir a verificação de uma quantidade exponencial de subconjuntos.