Versão restrita do problema Clique?

Considere a seguinte versão do problema Clique, em que a entrada é do tamanho e solicitamos que você encontre um clique do tamanho . A restrição é que o procedimento de decisão não pode alterar o gráfico de entrada em nenhuma outra representação e não pode usar nenhuma outra representação para calcular sua resposta, exceto os bits extras além do gráfico de entrada. Os bits extras podem ser usados, por exemplo, no algoritmo de força bruta para rastrear o status da pesquisa exaustiva por um clique, mas o procedimento de decisão é bem-vindo para usá-los de qualquer outra maneira que ainda resolva o problema. $n$ $k$ $\log(n^k)$

Há algo conhecido neste momento sobre a complexidade disso? Algum trabalho foi feito sobre outras restrições do Clique e, em caso afirmativo, você poderia me indicar esse trabalho?

complexity-theory time-complexity Pessoa tímida
fonte

Você pretende que a constante in seja igual ao tamanho da clique ?

k

$k$

\lg n^{k}

$\lg n^k$

k

$k$

Lucas Cook

@LucasCook Sim.

ShyPerson 2/12/12

Parece que você está perguntando se o problema de clique NP-completo pode ou não ser resolvido no espaço logarítmico. Usando máquinas de Turing, uma fita é somente leitura e armazena o gráfico de entrada. A outra fita é delimitada, de modo que haja espaço disponível para alguma constante . A classe de problemas solucionáveis neste modelo é conhecida como , espaço logarítmico determinístico. (Veja a Wikipedia ou no zoológico de complexidade ) $c \lg n$ $c$ $L$

Não se sabe se , mas uma resposta positiva implicaria que , então você (quase certamente?) Não encontrará uma resposta. e implica , o que implica . $\mathrm{CLIQUE} \in L$ $P = NP$ $L \subseteq P \subseteq NP$ $\mathrm{CLIQUE} \in L$ $\mathrm{CLIQUE} \in P$ $P = NP$

Edite caso eu tenha interpretado mal o problema:

Se você pretende que em seja igual ao tamanho do clique (ou seja, a quantidade de memória é escalonada com a entrada ), existe um algoritmo simples de força bruta: você pode percorrer todos conjuntos possíveis de nós e verifique se eles formam um -clique. Um ponto de partida para a busca de melhores soluções pode ser as referências de [1]. $k$ $\lg n^k = k \lg n$ $k$ $k$ $k$ $k$

[1] Virginia Vassilevska, "Algoritmos eficientes para problemas de clique" link em pdf

Lucas Cook
fonte

@ShyPerson Ok. A cadeia de entrada é muitas vezes imutável em modelos com espaço restrito (como TMs espaço sublinear em

), para que possa ser um bom lugar para olhar. Não tenho certeza de uma maneira formal de dizer que "você não pode fazer outra representação" além de simplesmente limitar o espaço. Se me permitem o espaço para fazer outra cópia de

, o que constitui exatamente outra representação? E se eu "acidentalmente" construir uma representação suficiente para um gráfico particularmente esparso ou compressível?

L

$L$

N L

$NL$

G

$G$

Lucas Cook

não está completo com NP! (a menos que

)

k C L I Q U E

$\mathrm{kCLIQUE}$

P = N P

$\mathrm{P}= \mathrm{NP}$

Alex ten Brink

@AlextenBrink Você quer dizer que o kCLIQUE é o problema da função? Mudei o nome para CLIQUE acima (sempre os confundo!), Mas é estranho para mim dizer que o kCLIQUE está no NP, se você quer dizer o problema da função.

Lucas Cook

searchProblema significativo , neste caso.

Lucas Cook

é o problema

para

fixo, enquanto que

tem

como parte da entrada. Ao verificar todos os subgrafos de tamanho

você tem um

algoritmo, que é polinomial se

é fixa, mas superpolynomal se, por exemplo

k C L I Q U E

$\mathrm{kCLIQUE}$

C L I Q U E

$\mathrm{CLIQUE}$

k

$k$

C L I Q U E

$\mathrm{CLIQUE}$

k

$k$

k

$k$

O (n^{k})

$O(n^k)$

k

$k$

k = Θ (n)

$k=\Theta(n)$

Alex ten Brink

Versão restrita do problema Clique?

Respostas: