Classes de complexidade para casos diferentes de "pior caso"

10

Temos classes de complexidade com relação a, digamos, complexidade de caso médio? Por exemplo, existe uma classe de complexidade (nomeada) para problemas que levam o tempo polinomial esperado para decidir?

Outra questão considera a complexidade do melhor caso , exemplificado abaixo:

Existe uma classe de problemas (naturais) cuja decisão requer pelo menos tempo exponencial?

Para esclarecer, considere um idioma completo EXP- . Obviamente, nem todas as instâncias de L exigem tempo exponencial: há instâncias que podem ser decididas mesmo em tempo polinomial. Portanto, a melhor complexidade de L não é o tempo exponencial.eueueu

Edição: Desde que surgiram várias ambiguidades, quero tentar esclarecer ainda mais. Por complexidade do "melhor caso", refiro-me a uma classe de complexidade cuja complexidade dos problemas é mais limitada por alguma função. Por exemplo, defina BestE como a classe de idiomas que não pode ser decidida em tempo inferior a um exponencial linear. Simbolicamente, seja uma máquina de Turing arbitrária, ec , n 0 e n sejam números naturais:Mcn0 0n

euBestE (c)(M)[(eu(M)=eu)(n0 0)(n>n0 0)(x{0 0,1 1}n)[T(M(x))2c|x|]]

onde indica o tempo que leva antes de M parar na entrada x .T(M(x))Mx

Aceito que definir essa classe de problemas seja muito estranho, pois exigimos que toda máquina de Turing , independentemente de seu poder, não possa decidir a linguagem no tempo menos que um exponencial linear.M

No entanto, observe que a contraparte em tempo polinomial ( BestP ) é natural, pois toda máquina de Turing exige tempo pelo menos ler sua entrada.|x|

PS: Talvez, em vez de quantificar como "para toda a máquina de Turing ", tenhamos de limitá-la a alguma classe pré-especificada de máquinas de Turing, como máquinas de Turing em tempo polinomial. Dessa forma, podemos definir classes como B e s t ( n 2 ) , que é a classe de linguagens que exigem pelo menos o tempo quadrática para ser decidido em máquinas de Turing de tempo polinomial.MBest(n2)

PS2: Também se pode considerar a contrapartida da complexidade do circuito, na qual consideramos o menor tamanho / profundidade do circuito para decidir um idioma.

MS Dousti
fonte
Só porque existem casos de SAT fáceis, isso não significa que o tempo esperado seja polinomial. Não sei se entendi sua pergunta ..
Lev Reyzin
@ Lev Reyzin: Eu não quis dizer que o SAT está no poli-time esperado. Eu quis dizer, como o SAT tem instâncias fáceis, não podemos dizer que a complexidade do "melhor caso" é difícil.
MS Dousti 20/09/10
Oh, entendo, a complexidade média dos casos e a melhor complexidade dos casos são duas perguntas separadas! De alguma forma, eu perdi isso na minha primeira leitura - meu erro.
Lev Reyzin
Não consigo analisar sua definição de BestE. M e x estão fora de sua quantificação ... também, você não quer que rejeite entradas que não estão em L ? Meu
Ryan Williams
@ Ryan: Obrigado por apontar a falha. Eu corrigi isso.
MS Dousti 20/09/10

Respostas:

13

Embora eu não consiga analisar suas definições, você deve saber que hierarquias de tempo muito mais fortes são conhecidas, em particular hierarquias de tempo "quase todos os lugares".

Aqui está a declaração formal: para cada vez que está vinculado , existe uma linguagem L T I M E [ T ( n ) ] com a propriedade de que todo algoritmo determinístico que reconhece L corretamente deve executar no tempo assintoticamente maior que t ( n ) em todas as entradas, com exceção de finitas, por tempo suficientemente pequeno t ( n ) . T(n)LTIME[T(n)]Lt(n)t(n)

"Suficientemente pequeno" significa .t(n)logt(n)o(T(n))

Suponha-se que escolher para um exemplo, e obter uma língua difícil L . Então, qualquer algoritmo que reconheça L corretamente deve levar pelo menos 2 n / n 2 em todas as entradas após um determinado comprimento. Parece ser o que você está procurando na sua classe BestE.T(n)=2nLL2n/n2

Referência:

John G. Geske, Dung T. Huynh, Joel I. Seiferas: uma nota sobre conjuntos quase complexos em todos os lugares e separando classes determinísticas de complexidade de tempo Inf. Comput. 92 (1): 97-104 (1991)

Ryan Williams
fonte
Muito bem, obrigado. Eu acho que você muito bem entendido a minha pergunta, e sua frase da introdução de "eu não consigo analisar as suas definições" é apenas um sinal de sua modéstia :)
MS Dousti
2
Desde que eu tenha adivinhado corretamente, sua definição deve ser algo como: "L \ no BestE \ iff (\ existe c) (\ forall M) [(L (M) = L) \ Rightarrow (\ existe n_0) (\ forall n > n_0) (\ forall x \ in \ {0,1 \} ^ n) [T (M (x))> 2 ^ {c | x |})]. "
Ryan Williams
Sim, você está certo. Editei a definição no último minuto e extraviei alguns dos quantificadores. Corrigi a pergunta com base na sua definição.
MS Dousti 20/09/10
12

Existem várias classes que tentam abordar várias noções de complexidade de casos médios. No Zoológico de Complexidade, algumas classes nas quais você pode se interessar são:

AvgP

HeurP

DistNP

(NP, amostrável em P)

Arora / Barak abrange muitas classes semelhantes (no capítulo 18), definindo distP, distNP e sampNP.

A relação exata entre todas essas classes é caracterizada pelos Cinco Mundos de Impagliazzo, que foram questionados anteriormente em outra questão .

Quanto à questão da complexidade do "melhor caso", não sei ao certo o que você quer dizer. Você está procurando EXP ?

Se você quer dizer classes de complexidade definidas em termos de melhor caso de tempo de execução em todas as instâncias, essa não é uma medida de complexidade muito boa a priori, já que você está analisando apenas os casos triviais de qualquer problema.

Daniel Apon
fonte
Muito bem feito! Era disso que eu precisava para a parte da complexidade da questão média. Quanto à parte do "melhor caso", notei que a afirmação original da pergunta era vaga. Foi mal! Eu o editei bastante, então considere a leitura novamente.
MS Dousti 20/09/10
5

[Expandindo a resposta de Ryan Williams e adicionando alguns termos de pesquisa para você] Sua noção de complexidade do melhor caso já tem um nome: quase todos os lugares (ae) dureza ou bi-imunidade. (Exemplo de Ryan é de -bi-imunidade). Se C é uma classe de complexidade, em seguida, uma linguagem L é C imune a se não houver subconjunto infinito L 'L tal que L 'C . L é C -bi-imune se L e seu complemento ¯ LTEuME[T(n)]CeuCeueuLCLCL são C imune a. Por exemplo, não é difícil mostrar que sua definição de B e s t E é equivalente à classe deconjuntos imunes a E -bi.L¯=ΣLCBestEE

(Histórico à parte: a noção de imunidade foi desenvolvida por Post em 1944 na teoria da computabilidade, muito antes de P ser definido. Post realmente considerado "conjuntos simples" - um conjunto é simples se seu complemento é imune. Para um teórico da computabilidade, a palavra "imune" geralmente significa "imune a conjuntos computáveis". Nesse cenário, a imunidade é equivalente a "imune a conjuntos de ce", já que todo conjunto de ce infinito contém um conjunto infinito computável. Acredito que o artigo de Post também foi o primeiro a noção de redução de muitos, mas não pude jurar.)

Joshua Grochow
fonte
Na verdade, sua definição apenas aceita entradas em L , não rejeita entradas não em L ... desde que você coloque a condição M ( x ) = 1 no lugar certo. MeueuM(x)=1 1
Ryan Williams
eueuC
11
@Sadeq: fixo, obrigado. @Ryan: Verdadeiro (ou foi há algumas horas: ele atualizou a definição). Então seria imunidade em vez de bi-imunidade. De qualquer forma, principalmente eu só queria apontar a palavra-chave "imunidade".
Joshua Grochow 20/09/10
2

Casos diferentes fazem mais sentido quando se trata de algoritmos, não de problemas. Por outro lado, as classes de complexidade são sobre problemas, não algoritmos. Portanto, a classe de complexidade sempre sendo a pior das hipóteses para qualquer algoritmo se deve à definição.

Em complexidade, seu objetivo é saber o número de recursos necessários para resolver qualquer instância de um determinado problema. Portanto, você sabe que, para qualquer instância e algoritmo, precisará desses recursos e nada mais.

Na análise de algoritmos, seu objetivo é garantir que seu algoritmo tenha um limite superior para um recurso, em qualquer instância do problema. Um limite trivial é a classe de complexidade do problema, já que nenhum algoritmo útil (que executa etapas desnecessárias) leva mais tempo que isso. No entanto, você pode melhorar esse limite, dadas as especificidades do algoritmo.

Θ

Quanto ao melhor caso, é trivial para todo problema encontrar o menor número de recursos necessários. Suponha que a entrada seja do comprimento O (n) e a saída do comprimento O (m). Em seguida, o seguinte TM M sempre é executado em O (n) + O (m) para o melhor caso:

M {Entrada, Instância, Solução}

  1. Compare a instância fornecida com a instância codificada na máquina.
  2. Se forem iguais, retorne a solução codificada.
  3. Senão, faça uma busca por força bruta.
chazisop
fonte
-1

O(1 1)

umar
fonte
11
Eu não acho que isso conte como um algoritmo correto para o problema. No entanto, seu algoritmo pode ser modificado para que primeiro verifique se a entrada é igual à instância específica que você predeterminou (no tempo O (1)). Se for, ele gera a resposta pré-computada. Caso contrário, você resolve a instância especificada por qualquer meio. Pensando nisso, qualquer algoritmo correto é executado no tempo O (1) para cada instância, se pudermos usar constantes diferentes atrás da notação O para diferentes instâncias. É por isso que a “complexidade do melhor caso”, no sentido literal, não é útil.
Tsuyoshi Ito
Se você está falando de computação determinística e não probabilística, levaria tempo linear (O (n) tempo) para verificar se duas codificações de instâncias são equivalentes: varre os n bits da codificação de entrada e verifique se é o mesmo como a codificação programada, não?
Daniel Apon
2
@ Daniel: Sim, mas se uma das instâncias for corrigida, leva apenas um tempo constante, onde a constante depende do comprimento da instância fixa.
Tsuyoshi Ito