Este algoritmo para Exact Three Cover é subexponencial, porque encontro combinações de $length(s)/3$ para $C$?

Question

Dada uma entrada $S$ (conjunto de elementos) encontre exatamente três capas para uma lista de conjuntos de 3 elementos nomeados $C$.

$S$ = 1,2,3,4,5,6

$C$ = [1,2,3],[4,5,6],[3,1,2]

Algoritmo

1. Classifique a lista e exclua ocorrências de conjuntos que se repetem em $C$.

• (por exemplo. $[1,2,3]$ repete por causa $[3,1,2]$.Claro, deixe um dos conjuntos.)

2. Remova conjuntos que possuem elementos que não existem em $S$.

• (por exemplo: $[1,2,9]$... $9$ não existe em $S$)

3.Remova conjuntos com elementos repetidos.

• (por exemplo. $[1,2,2]$ é excluído de $C$)

4.Remover conjuntos repetidos

• (por exemplo. $[1,2,3]$ e $[1,2,3]$ mas vá embora $[1,2,3]$)
• Depois $C$ foi classificado;o comprimento do pior caso $C$ vai ser$\frac{comprimento(s)!}{\esquerda(3!\esquerda(comprimento(s)-3\direita)!\direita)}$

5.Use $comprimento(s)$/$3$ para $K$ combinações de $C$.

• (por exemplo.haverá $2$ conjuntos necessários para uma capa exata de três$S$ $[1,2,3]$,$[4,5,6]$)

Parece que o número de combinações será < $2$^$\frac{comprimento(s)!}{\esquerda(3!\esquerda(comprimento(s)-3\direita)!\direita)}$ Pelo menos a maior parte do tempo.

Pergunta

Este algoritmo é subexponencial, pelo menos em média?

Answer 1

Não.O tempo exponencial às vezes é usado para significar tempos de execução em $2^{ eta(n)}$, e outras vezes é usado para significar tempos de execução em $2^{ eta(n^k)}$ para alguma constante $k>0$.

Seu algoritmo é exponencial em relação ao valor.a segunda definição e w.r.t. superexponencialo primeiro.Na verdade, seu algoritmo leva tempo $2^{ eta(n^3)}$, onde $n = |S|$ (notar que $\frac{n!}{3!\cdot (n-3)!} = \frac{n(n-1)(n-2)}{6} = eta(n^3)$).