Houve algum esforço para mostrar (usando o Switching Lemma), por exemplo, que SAT ou 3SAT não podem ter uma redução de AC para 2SAT? Quais são os problemas ou dificuldades envolvidos?
SAT e 3SAT estão completos para NP e 2SAT está completo para NL sob reduções AC . Portanto, essa prova separaria NP de NL .
No caso de uma redução de 3SAT para 2SAT em AC , o ventilador inferior é limitado por 3 (pelo menos antes da primeira comutação).
complexity-theory
satisfiability
Martin Seymour
fonte
fonte
Respostas:
É difícil ver como você usaria o fato de que o objetivo da redução é 2SAT em vez de, por exemplo, 3SAT.
A maneira comum de aplicar o lema de comutação é aproximadamente isso. Aplique uma restrição aleatória que corrija tudo, exceto umλ fração das entradas, para algum pequeno parâmetro λ que depende dos parâmetros (tamanho e profundidade) dos circuitos CA 0 em questão. Então, com probabilidade constante, a função calculada pelo circuito AC 0 se torna constante.
Aplicando isso no nosso caso, corrigimos tudo, excetoλ n dos insumos e, em troca, alguns μ fração das saídas é fixa. E agora? Não sabemos nada sobre a redução, portanto não está claro como obter uma contradição. Além do mais, não vejo como você usaria o fato de que o problema-alvo é 2SAT em vez de, digamos, 3SAT; nesse caso, não pode haver contradição.
O lema de comutação é o melhor quando você tem uma função concreta em mente e deseja provar limites inferiores de AC 0 para essa função específica. Outro uso, menos típico, do lema de comutação é provar algumas propriedades gerais de qualquer função calculada por um circuito AC 0 . O exemplo mais famoso é Linial-Mansour-Nisan, que dá limites à taxa de decaimento do espectro de Fourier. Não está claro como você usaria informações como essa no seu caso.
fonte
algum outro ângulo / ponto de vista sobre a sua pergunta, não levando isso em sentido estrito / literal. uma construção semelhante a um lemma de comutação "coincidentemente" foi encontrada no centro de uma prova célebre / muito avançada da teoria da complexidade, mostrando um limite inferior exponencial necessário para um problema semelhante ao SAT em circuitos monótonos, descoberto inicialmente por Razborov, que venceu o prêmio Nevanlinna para este ano atrás. no entanto, sua prova inicial não foi entendida como sendo dessa forma e levou muitos anos de reanálise em vários artigos para trazer essa conexão. esse esforço está resumido neste artigo: Complexidade monótona por Switching Lemma / Harnik, Raz. como citado em seu artigo, está ligado a uma reformulação de Berg e Ulfberg [BeUl97].
portanto, o lema de mudança e as reformulações continuam sendo uma área ativa de pesquisa e um "dispositivo" básico na separação de classes de complexidade e, portanto, provavelmente não seria aconselhável descartar completamente seu uso no futuro (importante? / significativo?) resultados de separação. sua pergunta também toca em P vs L, que também está aberta e é considerada por muitos possivelmente tão difícil quanto P vs NP (ambas as perguntas foram abertas quase na mesma quantidade de tempo, aproximadamente ~ 4 ½ décadas). no entanto, algumas limitações da técnica podem ser vistas na barreira de provas naturais identificada por Razborov / Rudich.
quanto ao 3SAT vs 2SAT, como você pergunta na sua pergunta, é claro que o 2SAT está em P e o 3SAT está em NP completo; portanto, qualquer "redução" significativa provavelmente também relacionaria P vs NP. Com base na sua ideia NP vs NL, existem outras áreas ativas de pesquisa que abordam a questão P vs NL, por exemplo, esta análise recente de Wehar, resultados de dureza para não-vazio por interseção
quanto às reduções de CA 0 e suas implicações para separações de classes de complexidade (aberta), existem algumas conexões observadas neste resultado recente: um teorema de hierarquia de profundidade de caso médio para circuitos booleanos / Rossman, Servedio, Tan (por exemplo, p5)
fonte