Existem problemas para os quais a divisão e conquista / recursão é comprovadamente inútil?

Quando tentamos construir um algoritmo para um novo problema, dividir e conquistar (usando recursão) é uma das primeiras abordagens que tentamos. Mas, em alguns casos, essa abordagem parece infrutífera à medida que o problema se torna muito mais complicado à medida que sua entrada cresce.

Minha pergunta é: existem problemas para os quais podemos provar que uma abordagem de dividir e conquistar não pode ajudar a resolver? Nas linhas seguintes, tento tornar isso mais formal.

Seja um certo problema cuja entrada tenha tamanho (por exemplo, um problema que aceite uma entrada com uma matriz de números). Suponha que tenhamos um algoritmo recursivo para resolver . O tempo de execução recursivo desse algoritmo é calculado assumindo um oráculo que pode resolver para cada em tempo constante. Por exemplo: $P(n)$ $n$ $n$ $P(n)$ $P(k)$ $k<n$

O tempo de execução recursivo da pesquisa binária é , pois utiliza apenas uma comparação e duas chamadas recursivas. $O(1)$
O elemento máximo em uma matriz pode ser encontrado no tempo recursivo . $O(1)$
O tempo de execução recursivo da classificação por mesclagem é , devido à etapa de mesclagem. $O(n)$

O tempo recursivo é geralmente menor que o tempo de execução real, o que reflete o fato de que o algoritmo recursivo é mais simples do que uma solução não-recursiva direta para o mesmo problema.

Agora minha pergunta é:

Existe um problema que pode ser resolvido no tempo , mas provavelmente não possui algoritmo recursivo com tempo de execução recursivo assintoticamente menor que ? $f(n)$ $f(n)$

Algumas variantes específicas desta pergunta são:

Existe um problema em que não possui algoritmo com tempo de execução recursivo ? (Talvez classificando?) $P$ $O(1)$
Existe um problema com um algoritmo exponencial que não possui algoritmo com tempo de execução recursivo polinomial?

EDIT: ao contrário do meu palpite, a classificação tem um algoritmo com tempo de execução recursivo $O(1)$ . Portanto, ainda está aberto, se existe algum problema em que não possua algoritmo com tempo de execução recursivo . $P$ $O(1)$

cc.complexity-theory recursion Erel Segal-Halevi
fonte

Talvez provando um kernelization limite inferior faria o truque en.wikipedia.org/wiki/Kernelization

Tyson Williams

O tamanho da saída é um limite inferior no tempo de execução. Portanto, qualquer problema com o tamanho da saída que corresponda à sua complexidade possui essa propriedade.

Chao Xu

@Chao Xu: Por que seu argumento não se aplica ao tamanho da entrada? Penso que o argumento depende de qual modelo de custo (e modelo computacional) consideramos.

Tsuyoshi Ito

É o oposto do que você está procurando, mas, considerando esses oráculos, seu modelo pode resolver a soma de um subconjunto - um problema conhecido de NP-Complete - em tempo linear, assumindo que P! = NP é muito mais poderoso do que as funções iterativas nesse caso. . A função simplesmente verifica se o conjunto atual é adicionado a 0; caso contrário, ele se chama nos subconjuntos n do tamanho n-1. O tempo de execução em si é n! no entanto, o que é pior que a força bruta, por isso não tenho certeza do valor que esse modelo fornece, mas ainda é uma pergunta interessante.

Phylliida

Sua edição recente ("recursiva" -> "dividir e conquistar") é uma grande mudança na questão. Gostaria apenas de postar uma pergunta separada. Provavelmente, podemos dizer coisas sobre dividir e conquistar, observando, por exemplo, as profundezas dos circuitos.

usul

Respostas:

Existe um problema com um algoritmo exponencial que não possui algoritmo com tempo de execução recursivo polinomial?

Sim. Observe que se uma linguagem de registro possui “algoritmo recursivo” com “tempo de execução recursivo” polinomial, então está em P. Há um idioma de registro em E ∖ P por um argumento padrão de diagonalização.

Existe um problema que pode ser resolvido no tempo , mas provavelmente não possui algoritmo recursivo com tempo de execução recursivo ? $f(n)$ $o(f(n))$

Pode depender do modelo computacional, mas duvido que isso seja conhecido, uma vez que o teorema da hierarquia de tempo para máquinas de Turing com duas fitas não é poderoso o suficiente para distinguir, digamos, O ( n ² ) tempo e o ( n ² ) tempo, mesmo sem dar a este último o acesso constante às respostas em instâncias menores.

Comentários aleatórios sobre suas perguntas neste post:

Não creio que essas questões estejam relacionadas à utilidade de programas recursivos, apesar do que o título do post e sua escolha de terminologia sugerem. Como a BVMR escreveu em uma resposta, recursões e iterações são equivalentes em certo sentido. Em vez disso, acho que as perguntas têm uma conexão com a utilidade da abordagem de dividir e conquistar.
Na teoria da complexidade, uma noção relacionada à sua noção de "algoritmos recursivos" com seu "tempo de execução recursivo" é chamada de "auto-reduções que diminuem o comprimento" com sua complexidade de tempo.
Alguma parte de suas perguntas (definitivamente a parte referente a algoritmos de tempo sublinear) depende da escolha do modelo computacional.

Tsuyoshi Ito
fonte

Em relação à sua primeira resposta: deixe-me tentar expandi-la para ver se entendi corretamente. Suponha que uma determinada linguagem de registro possua um algoritmo com "tempo de execução recursivo" polinomial. Um algoritmo polinomial para essa linguagem pode ser construído usando programação dinâmica. A resposta para

pode ser encontrada em tempo polinomial, pois não são necessárias chamadas recursivas. A resposta para

pode ser encontrada em tempo polinomial usando a resposta para

. Em seguida, para responder

podem ser encontradas em tempo polinomial usando as respostas para

n = 0

$n=0$

n = 1

$n=1$

n = 0

$n=0$

n = 2

$n=2$

n = 1

$n=1$

n = 0

$n=0$ etc. Está correto?

Erel Segal-Halevi

Sim, embora seja melhor evitar noções assintóticas, como "tempo polinomial", quando você fala sobre um valor específico de n; por exemplo, não faz sentido dizer "o algoritmo é executado no tempo polinomial quando n = 0". Se uma linguagem de registro possui um "algoritmo recursivo" com "tempo de execução recursivo" polinomial p (n), então podemos calcular a resposta para n sem o oracle calculando as respostas para 0, 1, 2, ..., n, e isso leva tempo

, que é polinomial em n.

O (\sum_{i = 0}^{n} p (i))

$O(\sum_{i=0}^n p(i))$

Tsuyoshi Ito

Obrigado. Concordo com o seu comentário sobre dividir e conquistar e editei a pergunta de acordo.

Erel Segal-Halevi

Qualquer pergunta que tenha resposta recursiva tem resposta iterativa e vice-versa.

Qualquer algoritmo recursivo pode ser reescrito de maneira iterativa e vice-versa.

Portanto, sua pergunta não está boa.

BVMR
fonte

A complexidade de um algoritmo, como eu o defini na pergunta, geralmente não permanece a mesma quando é convertida de iterativo para recursivo. Por exemplo, o máximo de n elementos pode ser encontrado por um algoritmo iterativo com operações O (n), mas também pode ser encontrado por um algoritmo recursivo com operações O (1) (uma das quais é uma chamada recursiva). Embora finalmente o tempo de execução de ambos os algoritmos seja o mesmo, o algoritmo recursivo é mais simples de programar porque possui menos operações.

Erel Segal-Halevi

-2

Não tenho certeza se entendi corretamente sua noção de "complexidade recursiva".

Permite (razoavelmente) supor uma linguagem de programação que contenha um esquema para recursão primitiva, isto é, na qual é possível definir funções de $f$

f (0, \vec{x}) = c (\vec{x}) f (n + 1, \vec{x}) = g (f (n, \vec{x}), n, \vec{x})

$f(0,\vec x) = c(\vec x)\\ f(n+1,\vec x) = g(f(n,\vec x),n,\vec x)$

$c$ $g$ $\mathcal{O}(1)$ $\mathcal{O}(1)$

Se todas as minhas suposições forem atendidas, o exemplo que você está procurando não pode ser recursivo primitivo.

DFF
fonte

por favor, elabore os votos negativos

DFF #

P (k)

$P(k)$

k < n

$k<n$

g (f (n, x), n, x)

$g(f(n,x),n,x)$

f (n, x)

$f(n,x)$ que tem tempo de execução constante. Não diminuí a votação, mas esta é uma pergunta respondida de um ano e você também interpretou mal uma determinada definição.

chazisop 12/01

g

$g$

O (1)

$\mathcal{O}(1)$

f (n, x)

$f(n,x)$

O (1 \circ 1) = O (1)

$\mathcal{O}(1\circ 1)=\mathcal{O}(1)$

g

$g$

O (1)

$O(1)$

ahh, ok ... agora tudo faz sentido ... obrigado pelo esclarecimento ... provavelmente fiquei confuso pelo fato de que a complexidade recursiva não ser invocada recursivamente ^^ (que não é muito celar da definição imo)

DFF