Caracterização de problemas para os quais existem algoritmos de tempo sublinear

Eu queria saber se os problemas para os quais existem algoritmos de tempo sublinear (no tamanho da entrada) podem ser caracterizados como possuindo propriedades específicas. Isso inclui tempo sublinear (por exemplo, teste de propriedades, uma noção alternativa de aproximação para problemas de decisão), espaço sublinear (por exemplo, algoritmos de esboço / streaming nos quais a máquina de Turing tem uma fita somente leitura, um espaço de trabalho sublinear e uma saída somente gravação fita) e medições sublineares (por exemplo, recuperação esparsa / sensoriamento compressivo). Em particular, estou interessado em tal caracterização tanto para a estrutura de algoritmos de teste de propriedades quanto para o modelo clássico de algoritmos aleatórios e de aproximação.

Por exemplo, os problemas para os quais existe uma solução de programação dinâmica exibem uma subestrutura ideal e subproblemas sobrepostos; aqueles para os quais existe uma solução gananciosa exibem a subestrutura ideal e a estrutura de um matróide. E assim por diante. Qualquer referência relacionada a este tópico é bem-vinda.

Com exceção de alguns problemas que admitem um algoritmo sub-linear determinístico, quase todos os algoritmos sub-lineares que eu vi são randomizados. Existe alguma classe de complexidade específica relacionada a problemas de admissão de algoritmos de tempo sublinear? Se sim, essa classe está incluída no BPP ou PCP?

cc.complexity-theory ds.algorithms complexity-classes approximation-algorithms Massimo Cafaro
fonte

tempo sub-linear em que modelo?

Kaveh

Os algoritmos de teste de propriedade estão na estrutura geral do que você deseja, mas o argumento de Kaveh deve ser respondido primeiro.

precisa saber é o seguinte

Eu editei minha pergunta adicionando as informações solicitadas.

Massimo Cafaro

A transformada de Fourier de um vetor pode ser calculada em tempo sublinear quando é (quase)

separado no domínio da frequência. Portanto, a propriedade aqui é escassa. Verifique, por exemplo, "Algoritmo simples e prático para a transformada esparsa de Fourier", de Haitham Hassanieh, Piotr Indyk, Dina Katabi e Eric Price nms.lcs.mit.edu/~dina/pub/soda12.pdf e suas referências.

k

$k$

precisa

Respostas:

Para a tarefa de teste constante das propriedades do gráfico, é conhecida uma caracterização interessante. Uma propriedade de gráfico é uma função de todos os gráficos para , e uma propriedade de gráfico é testável se houver um algoritmo aleatório tal que para todos e todos os gráficos : $\{0,1\}$ $P$ $A$ $\varepsilon > 0$ $G$

lê apenas arestas de para alguma função $A(G)$ $g(\varepsilon)$ $G$ $g$
Se então saídas `` Sim '', com elevada probabilidade (por exemplo, pelo menos ) $P(G)=1$ $A(G)$ $2/3$
Se pelo menos arestas de devem ser adicionadas ou removidas para obter um tal que (isto é, é longe da propriedade ), então gera `" não "com probabilidade de pelo menos $\varepsilon n^2$ $G$ $G'$ $P(G')=1$ $G$ $\varepsilon$ $A(G)$ $2/3$

Ou seja, pode distinguir entre gráficos que têm e gráficos que têm alto distância de edição de gráficos com . Alon, Fischer, Newman e Shapira provaram que uma propriedade é testável dessa maneira se, e somente se, a propriedade puder ser "reduzida" à propriedade de verificar se um gráfico tem uma partição regular (no sentido de Szemeredi) . Isso mostra que a regularidade do teste é "completa" para o teste, em algum sentido. (Também há uma versão de erro unilateral da testabilidade, consulte a referência.) $A$ $P$ $P$ $P$ $\varepsilon$

Ryan Williams
fonte

No domínio do espaço sublinear , não há uma classe explícita de problemas que admitem uma solução espacial sublinear, mas existem grandes classes de problemas (estimativa do momento da frequência, redução da dimensionalidade etc.) em que a existência de um pequeno "esboço" pode ser mostrada e isso leva a algoritmos eficientes.

Mas também neste espaço, todos os algoritmos são aleatórios, e existem limites inferiores determinísticos fortes, baseados principalmente na complexidade da comunicação.

Suresh Venkat
fonte