Para quais problemas em P é mais fácil verificar o resultado do que encontrá-lo?

52

Para (versões de pesquisa) de problemas completos de NP , verificar uma solução é claramente mais fácil do que encontrá-la, pois a verificação pode ser feita em tempo polinomial, enquanto que encontrar uma testemunha leva (provavelmente) tempo exponencial.

Em P , no entanto, a solução também pode ser encontrada em tempo polinomial, portanto, não parece óbvio quando a verificação é mais rápida do que encontrar a solução. De fato, problemas diferentes parecem se comportar de maneira diferente desse ponto de vista. Alguns exemplos:

  1. 3SUM: dados números de entrada, encontre 3 dentre eles que somam 0. Até onde eu sei, o algoritmo mais rápido conhecido é executado no tempo O ( n 2 - o ( 1 ) ) e essa ordem é ideal conjecturada. Por outro lado, a verificação de uma solução é muito mais rápida, pois tudo o que precisamos fazer é apenas verificar se os 3 números encontrados realmente somam 0.nO(n2o(1))

  2. Caminhos mais curtos de todos os pares: dado um gráfico com pesos das arestas, calcule sua matriz de distância do caminho mais curto. Uma vez que tal matriz é dada, é possível verificar mais rapidamente se é de fato a matriz de distância correta do que recalculá-la? Meu palpite é que a resposta talvez seja sim, mas certamente é menos óbvia do que no 3SUM.

  3. Programação linear. Se uma solução ótima reivindicada é fornecida, é mais fácil verificar do que recalculá-la, quando também são fornecidas informações auxiliares (uma solução dupla ideal). Por outro lado, se apenas a solução principal está disponível, não está claro se é possível verificar mais rapidamente do que realmente resolver o LP.

Pergunta: o que se sabe sobre esse assunto? Ou seja, quando é mais fácil verificar uma solução para um problema em P do que encontrar a solução?

Andras Farago
fonte
7
kkk
16
nn1Θ(nlogn)
7
Deseja que seja fácil verificar instâncias sim e não para problemas de decisão? Para o 3SUM, embora seja fácil verificar instâncias yes em tempo constante, não sei se é fácil verificar uma instância no. Ou você está pensando mais na linha de problemas em que há uma saída não-booleana, como multiplicação de matrizes? (A multiplicação de matrizes é um exemplo do que você quer se você permitir algoritmos randomizados.)
Robin Kothari
3
"Por outro lado, a verificação de uma solução é muito mais rápida, pois tudo o que precisamos fazer é apenas verificar se os 3 números encontrados realmente somam 0." - Também precisamos verificar se os 3 números encontrados realmente fazem parte da entrada.
Hv
3
Existem problemas para os quais sabemos que a verificação não é mais fácil?
Raphael

Respostas:

24

α(n)

Suresh Venkat
fonte
4
Talvez seja justo acrescentar que existe um algoritmo aleatório que é executado no tempo linear esperado (o algoritmo de Karger-Klein-Tarjan).
Sasho Nikolov
2
Além disso, caso alguém queira um link, este é o algoritmo de verificação MST em tempo linear mais simples que eu conheço: webhome.cs.uvic.ca/~val/Publications/Algorithmica-MSTverif.ps .
Sasho Nikolov
20

Este trabalho mostra que existem algoritmos de verificação para ambos SIM e instâncias NO para 3 problemas, incluindo o fluxo máximo, 3SUM, e APSP, que são mais rápida por um factor de polinomial do que os limites conhecidos para o cálculo da solução propriamente dita.

Há uma classe de problemas, a saber, aqueles que melhoram o tempo de execução são SETH difíceis, cujo tempo de execução para verificar as instâncias de NO é improvável que seja significativamente mais rápido que o tempo para calcular a solução, caso contrário, a conjectura deste artigo chamada Não Determinística Hipótese de tempo exponencial forte falharia.

Thatchaphol
fonte
18

Para alguns problemas, parece não haver diferença. Em particular, Vassilevska Williams & Williams mostram:

  • para multiplicação de matriz booleana, calculando o produto da matriz e verificando o equivalente subcúbico do produto da matriz, o que significa que ambos têm algoritmos de tempo subcúbico ou nenhum deles.

  • O mesmo se aplica à computação e verificação de produtos matriciais sobre qualquer "estrutura estendida (min, +)" (consulte o documento para obter a definição, mas isso inclui muitos problemas naturais).

(Agora, é claro, é possível que todos esses problemas tenham algoritmos subcúbicos, e pode haver uma diferença polinomial entre computação e verificação, mas para esses problemas não pode haver uma diferença cúbica. E me parece plausível que, em todos eles requerem tempo essencialmente cúbico.)

Joshua Grochow
fonte
2
Por outro lado, para multiplicação de matrizes em um campo grande o suficiente, existe um algoritmo aleatório de tempo quadrático para verificação, enquanto o tempo de execução mais rápido para calcular o produto é n ômega.
precisa saber é o seguinte
2
@Thatchaphol: Sim, embora muitas pessoas acreditem em ômega = 2 ... Além disso, é amplamente reconhecido que a multiplicação de matrizes booleanas (isto é, a computação de matriz mult sobre o booleano e-ou semi-anel) tem uma natureza um pouco diferente da multiplicação de matrizes em um campo.
18730 Joshua Grochow #
16
  • Ω(n)Ω(logn)

    O(1)

  • Ω(nlogn)O(n)

Rafael
fonte
2
Ω(nlogn)O(1)
O(n)
Θ(n)
10

Eu acho que muitos exemplos vêm de problemas NP-completos que se enquadram em P quando corrigimos um ou mais parâmetros .

kkk

kP=NPkΩ(nk))

k

Marzio De Biasi
fonte
9

O~(n6)O~(n3)

Joe Bebel
fonte
o complemento (composição) é ainda mais fácil de testemunhar!
precisa
3

O(n2ϵ)

PΩ(n1ϵ)

O(n2/logn)

SamM
fonte