O acesso a um oráculo forneceria uma grande aceleração super polinomial para tudo em (assumindo que o conjunto não esteja vazio). No entanto, é menos claro quanto beneficiaria desse acesso ao oracle. Obviamente, a aceleração em não pode ser super-polinomial, mas ainda pode ser polinomial. Por exemplo, poderíamos encontrar um caminho mais curto mais rapidamente com um oráculo que sem ele? Que tal algumas tarefas mais sofisticadas, como minimização de função submodular ou programação linear? Eles (ou outros problemas naturais em ) se beneficiariam de um oráculo do ?N P - P P P S A T P S A T
De maneira mais geral, se pudermos encontrar algum problema em e usar um oráculo para ele, então qual dos problemas em poderia acelerar? P
cc.complexity-theory
np
np-complete
Andras Farago
fonte
fonte
Respostas:
Na verdade, a aceitação de máquinas de Turing não determinísticas no tempo é redutível ao SAT (a construção é feita por simulação inconsciente, veja Arora-Barak); portanto, sempre que uma máquina não determinística é apreciavelmente mais rápida que uma determinística primeiro, veremos pelo menos alguma aceleração com um oráculo SAT.O ( t log t )t O(tlogt)
Para ser mais concreto, o teste de primalidade vem à mente, pois a melhor variante do algoritmo AKS parece testar a primalidade de um número de bits no tempo . Mas se formos à "velha escola", Pratt deu uma MT não determinística para decidir a primalidade no tempo . A aceitação desta máquina pode ser reduzida (deterministicamente) no tempo para uma instância SAT.O ( n 6n O ( n 3O(n6polylogn) O ( n 3O(n3polylogn) O(n3polylogn)
O problema 3SUM pode ser outro exemplo, pois parece que se pode adivinhar uma solução e verificá-la em tempo subquadrático e, em seguida, a aceitação dessa máquina pode ser reduzida para SAT em tempo subquadrático.
fonte
Esta questão fica mais diretamente na representação e no tempo necessário para reduzir um problema para outro ...
A principal resposta que tenho em mente é um oráculo de Programação Linear / Inteiro. A versão de decisão desse problema é NP-completa. Há uma "redução" trivial da programação linear porque é um caso especial. Mas um oráculo apenas para programação linear (e muito menos para ILP) acelera muitos problemas que são imediatamente solucionáveis pela programação linear. Eles podem ser reduzidos a isso em tempo linear, reescrevendo o problema como um LP. Por exemplo, caminhos mais curtos e outros problemas de fluxo, correspondências.
Mas eu não acho que o ILP seja o único, de qualquer forma, provavelmente é mais do que as pessoas não pensaram muito em, por exemplo, reduzir o caminho mais curto para o TSP ou assim por diante.
fonte
Em uma nota relacionada (mais de um comentário, postando como resposta por solicitação), se em vez de um oráculo permitir um oráculo , ele poderá ser usado para encontrar circuitos mínimos para qualquer problema em (segue a mesma ideia que a prova de Karp-Lipton). Isso daria um custo amortizado quase ideal para qualquer problema; a razão pela qual ele é amortizado apenas é que, se você usar isso apenas uma vez, o tamanho da fórmula você será essencialmente o tempo de execução do algoritmo original de , mas após essa etapa, você terá um circuito ideal para todos instâncias de tamanho .Σ 2 S A T P Σ 2 S A T ≤ nSAT Σ2SAT P Σ2SAT ≤n
fonte