É mais difícil encontrar reduções do espaço de log do que reduções de P?

21

Motivado pela resposta de Shor relacionada a diferentes noções de completude de NP, estou procurando um problema que seja completo de NP em reduções de P, mas que não seja conhecido como completo de NP em reduções de espaço de log (de preferência por um longo período de tempo). Além disso, é mais difícil encontrar reduções no espaço de log entre problemas NP-completos do que encontrar reduções de P?

Mohammad Al-Turkistany
fonte
Redução de P significa função polinomial computável multi-one ou AKA como redução de Karp.
Mohammad Al-Turkistany 08/08
4
Eu acho que é um problema aberto ... e o !!! não autoritário !!! Wikipedia :-) :-) concorda: "... É uma questão em aberto se os problemas de NP-completos forem diferentes com relação ao espaço de log e reduções de tempo polinomial ...". Veja também Seixos e ramificação Programas de Avaliação da árvore para uma recente tentativa de separar L e P.
Marzio De Biasi
3
Eu acho que todos os famosos problemas de NP-complete estão realmente completos sob muitas reduções de AC0.
Kaveh
É trivialmente mais difícil encontrar reduções de espaço de log do que reduções de polytime, porque o espaço de log é mais restritivo. Dito isto, muitas das reduções de polytime que você vê usam apenas espaço logarítmico.
David Richerby
1
Qual é a prova de que as reduções do espaço de log são mais difíceis que as reduções de P? Como você pode fazer isso sem separar de P ? euP
Mohammad Al-Turkistany

Respostas:

21

Kaveh está correto ao dizer que todos os problemas "naturais" completos de NP são facilmente vistos como completos sob reduções (uniformes) de . No entanto, é possível construir conjuntos completos para NP em reduções de espaço de log que não estejam completas em A C 0AC0AC0 reduções de . Por exemplo, em [Agrawal et al, Computational Complexity 10 (2): 117-138 (2001)), uma codificação de SAT de correção de erros mostrou ter essa propriedade.

No que diz respeito a um candidato "provável" para um problema que é completo com reduções no tempo poli-tempo, mas não com reduções no espaço de log, pode-se tentar criar um exemplo da forma { : ϕ está em SAT e z está em CVP [ou algum outro conjunto completo de P] iff b = 1 , em que z é a sequência que resulta em cada segundo bit de ϕ }. Certamente, a maneira ingênua de mostrar que esse conjunto está completo envolverá o cálculo da redução usual para SAT e a construção de z e o cálculo do bit(ϕ,b)ϕzb=1zϕzb, que é inerentemente poli-tempo. No entanto, com um pouco de trabalho, esquemas como esse geralmente podem ser mostrados completos nas reduções do espaço de log por meio de alguma redução não ingênua. (Eu não elaborei esse exemplo em particular ...)

Eric Allender
fonte
Obrigado pela sua resposta agradável e adoro aceitá-la, mas esperarei por uma resposta que atenda diretamente à minha pergunta com um problema natural.
Mohammad Al-Turkistany
Problema natural na interpretação mais comum da palavra natural na teoria da complexidade.
Mohammad Al-Turkistany