Classe de complexidade correspondente à classificação

14

Duas partes do TCS são algoritmos e complexidade. Vou dizer de forma simplista que algoritmos é o estudo dos limites superiores, mostrando que você pode fazer algo (com recursos restritos) e a complexidade é mostrar que você não pode fazê-lo sem alguns recursos mínimos.

Com frequência, um problema algorítmico é declarado em um modelo de decisão para colocá-lo em uma classe de complexidade.

Mas algo que sempre me incomodou é que alguns algoritmos elementares nunca são mencionados diretamente como pertencentes a uma classe específica. Um exemplo é a classificação (comparação). Por mais que eu tente, uma classe relevante parece deficiente demais (na verdade, é apenas verificar no espaço de logs que o resultado está classificado? Isso parece fraco demais ou eu não estou conseguindo a versão correta da decisão).

Qual é a melhor / mais apropriada / mais útil classe de complexidade em que se encontra a classificação por comparação?

Mitch
fonte

Respostas:

17

O problema de ordenação é realmente completa para TC0 (sob -redução). Uma fonte padrão para isso é a Seção 1.4.3 do livro de Vollmer .AC0

Observe que é a classe de problemas de decisão, mas geralmente pensamos em classificar como um problema de função, ou seja, queremos exibir os números, digamos, em ordem não decrescente. No entanto, também podemos definir a classificação como um problema de decisão da seguinte maneira:TC0

Dada uma sequência de números e dois números k , p [ n ]a1,,ank,p[n] , queremos decidir se está na posição p na seqüência temos, classificando a 1 , ... , um n em não decrescente ordem. Note-se que a ambigüidade evitar, quando um i = a j , queremos um i para preceder um j se i < j .akpa1,,anai=ajaiaji<j

Dai Le
fonte
Excelente ... especificado como que problema formal de decisão?
Mitch
1
Seria o dobro excelente incluir uma referência em sua resposta.
Oleksandr Bondarenko
@ Mitch e @ Okeksandr: Obrigado por seus comentários! Acabei de estender minha resposta para esclarecer esses pontos.
Dai Le
Isso soa como o problema de decisão para estatísticas de pedidos. Existe um problema relacionado em que tudo está no lugar certo? Algo como dar uma sequência e uma permutação σ em [ 1 ..a1...anσ decidem se1 k < j n , a σ k < a σ j . Isso é tão difícil quanto o seu; é mais difícil ou completo para uma aula inclusiva? [1..n]1k<jn,aσk<aσj
Mitch
2
@ Mitch: Eu acredito que verificar se tudo está no lugar certo como esse é realmente mais fácil do que classificar. A intuição é que você pode verificar se para todo o par possível ( a σ k , a σ j ) com k < j em paralelo, o que eu acredito que pode ser feito em A C 0 . Para o problema de classificação acima, você precisa "contar" para descobrir a posição correta de um número na ordem linear. aσk<aσj(aσk,aσj)k<jAC0
Dai Le
0

Acredito que FP é o que você está procurando.

Nicholas Mancuso
fonte
Bem, eu estou procurando pela classe de complexidade de decisão relevante, e não pela funcional, mas mesmo assim, tenho certeza de que a classificação por comparação não está nem perto de P-complete (ou FP-complete), então estou esperando uma classe menor para a qual espera-se estar / completa para.
Mitch
Eu não sabia que a integridade era um dos requisitos para sua pergunta. Como um problema de decisão (se você desconsiderar sua restrição de integridade), por que P não seria aceitável como resposta? Dado um DTM, você pode produzir e validar um certificado em tempo polinomial.
Nicholas Mancuso
Dado um problema geral, o que eu normalmente quero saber não é apenas o tempo polinomial, mas a menor classe em que ele poderia estar. Gostaria de saber se está em LOGCFL, NL, L, AC_0, etc. é uma maneira de você "não poder" fazer melhor. Portanto, nit não é um requisito da minha pergunta, mas provavelmente uma resposta.
Mitch