Problemas não triviais solucionáveis em tempo constante?

Tempo constante é a complexidade absoluta de fim de tempo baixo. Alguém pode se perguntar: existe algo não trivial que pode ser calculado em tempo constante? Se nos apegarmos ao modelo da máquina de Turing, pouco poderá ser feito, pois a resposta só pode depender de um segmento inicial de comprimento constante da entrada, pois partes mais afastadas da entrada nem podem ser alcançadas em tempo constante.

Por outro lado, se adotarmos o modelo de RAM de custo unitário um pouco mais poderoso (e mais realista), no qual operações elementares em números de bits são contadas como etapas únicas, poderemos resolver tarefas não triviais, mesmo em tempo constante. Aqui está um exemplo: $O(\log n)$

Instância: Inteiros , cada um dado em formato binário por bits. $n, k, l, d$ $O(\log n)$

Pergunta: Existe um gráfico vértice, de modo que sua conectividade de vértice é , sua conectividade de borda é e seu grau mínimo é ? $n$ $k$ $l$ $d$

Observe que, a partir da definição, nem é óbvio que o problema esteja no NP . O motivo é que a testemunha natural (o gráfico) pode precisar de uma descrição longa de , enquanto a entrada é fornecida apenas por bits . Por outro lado, o seguinte teorema (veja Teoria dos Gráficos Extremais de B. Bollobas) vem em socorro. $\Omega(n^2)$ $O(\log n)$

Teorema: Seja inteiros. Existe um gráfico -vertex com conectividade de vértices , conectividade de borda e grau mínimo , se e somente se uma das seguintes condições for atendida: $n, k, l, d$ $n$ $k$ $l$ $d$

$0\leq k\leq l \leq d <\lfloor n/2 \rfloor$ ,
$1\leq 2d+2-n\leq k\leq l = d< n-1$
$k=l=d=n-1.$

Como essas condições podem ser verificadas em tempo constante (no modelo de RAM de custo unitário), o teorema leva a um algoritmo de tempo constante nesse modelo.

Pergunta: Quais são alguns outros exemplos não triviais de algoritmos de tempo constante?

cc.complexity-theory ds.algorithms time-complexity Andras Farago
fonte

A verificação de uma prova probabilisticamente verificável conta?

David Eppstein

Não pense que seu exemplo é

time. Sua entrada possui comprimento

; nesse caso, a palavra típica RAM permitiria apenas operações de bits

em uma etapa. (A alternativa é permitir que WordSize proporcional ao comprimento de entrada, mas, nesse caso, pode-se citar muitos algoritmos "em tempo constante" ...) Você poderia tentar adicionar uma cadeia de comprimento

depois esses números, mas então eu não vejo como verificar esse formato seria executado em

O (1)

$O(1)$

m = O (\log n)

$m=O(\log n)$

O (\log m)

$O(\log m)$

\geq n

$\geq n$

O (1)

$O(1)$ time: parece que você deve verificar (por meio de pesquisa binária, digamos) se o comprimento total da string é de fato

, o que requer

time.

Ω (\log n)

$\Omega(\log n)$

\log n

$\log n$

Ryan Williams

Penso que a sugestão de David Eppstein aponta para uma direção mais interessante: considerando algoritmos aleatórios de tempo O (1). Pelo menos nesse caso, você pode esperar que cada bit de entrada seja acessado em pelo menos uma execução possível do algoritmo.

Ryan Williams

Um exemplo simples de algoritmo aleatório de tempo O (1) é mediano aproximado (aproximado no sentido de que ele dividirá a entrada em aproximadamente 50-50). Simplesmente escolha aleatoriamente 1000000 elementos da entrada, calcule sua mediana e faça a saída.

Jukka Suomela

Eu gosto da sua pergunta, mas a desvantagem do seu exemplo é que ele depende de um teorema matemático. Empurrando isso para o limite, você poderia dizer: Instância Inteiros positivos

. Pergunta Existe um número inteiro

tal que

(a resposta é verdadeira ou falsa). Bem, existe de fato um algoritmo de tempo constante porque a resposta é sempre falsa, mas esse claramente não é o tipo de exemplo que você deseja.

x, y, z

$x, y, z$

n > 2

$n > 2$

x^{n} + y^{n} = z^{n}

$x^n + y^n = z^n$

J.-E.

Respostas:

O artigo Algoritmos de aproximação de tempo constante por meio de melhorias locais de Nguyen e Onak fornece muitos exemplos de esquemas aleatórios de aproximação de tempo constante: Correspondência máxima (o tempo de execução depende apenas do grau máximo do gráfico), Capa do conjunto, etc. apresentar um método para projetar tais algoritmos.

Lamine
fonte

Existem muitos exemplos de jogos estudados na teoria combinatória dos jogos em que o estado de um jogo pode ser descrito por um número constante de valores inteiros. Para alguns deles, uma estratégia vencedora para o jogo pode ser calculada em tempo constante. Mas eles também levantam questões sobre qual é exatamente o seu modelo de computação.

Um dos jogos combinatórios mais simples e básicos é o seguinte: um possui um número constante de pilhas de feijões e, em um único movimento, você pode remover qualquer número de feijões de uma pilha, ganhando ou perdendo (dependendo da sua escolha de regras) se você pegar o último feijão. A estratégia ideal pode ser calculada em tempo constante, se você permitir operações booleanas xor bit a bit (ou seja, o operador ^ em linguagens de programação como C / C ++ / Java / etc.) Esse é um algoritmo de tempo constante no seu modelo?

Aqui está um em que se sabe que existe um algoritmo determinístico exato em tempo constante (em um modelo de computação estendido possivelmente irreal que permite testar a primalidade de um número em tempo constante), mas não se sabe o que é esse algoritmo: dada uma partida movimento no jogo da cunhagem de Sylver , determine se é um movimento vencedor ou perdedor. Um fluxograma para esse problema é fornecido em Berlecamp, Conway e Guy, Winning Ways , mas depende de um conjunto finito de contra-exemplos para uma caracterização geral dos movimentos vencedores, e não se sabe qual é esse conjunto (ou mesmo se é esvaziar).

Outro exemplo interessante da teoria combinatória dos jogos é o jogo de Wythoff. Cada posição do jogo pode ser descrita por um par de números inteiros (ou seja, espaço constante, no seu modelo de computação), os movimentos no jogo envolvem a redução de um desses dois números inteiros para um valor menor, e a estratégia vencedora envolve a mudança para uma posição em que a razão entre esses dois números inteiros é o mais próximo possível da proporção áurea. Mas em muitas posições de jogo há uma opção: você pode reduzir o maior dos dois números inteiros até o ponto em que é (quase) o número inteiro menor multiplicado pela proporção áurea ou o número inteiro menor dividido pela proporção áurea. Apenas uma dessas duas opções será uma jogada vencedora. Portanto, a estratégia ideal pode ser definida em termos de um número constante de operações aritméticas, mas essas operações envolvem um número irracional, a proporção áurea. Esse é um algoritmo de tempo constante no seu modelo? Talvez isso' (uma aproximação à proporção áurea precisa para bits), mas não o tempo constante, usando apenas operações aritméticas (sem raízes quadradas) e valores fixos de constantes inteiras? $n$ $\log n$

David Eppstein
fonte

Obrigado, estes são exemplos interessantes. Eles também muito bem lançar luz ao fato de que o conceito de "constante de tempo" é menos claro do que eu pensava ...

Andras Farago

$|G|$ $G$ $p$ $m$ $m$ $|G|$ $G$ $p$ $m$ $G$ $|G|$ $m$ $m$ $m$

orgesleka
fonte

Problemas não triviais solucionáveis ​​em tempo constante?

Respostas:

Problemas não triviais solucionáveis em tempo constante?