Esta questão está intimamente relacionada a outro post: Transições de fase em problemas graves do NP, mas é um pouco diferente. Embora essa pergunta seja sobre a dureza de instâncias específicas de problemas difíceis de NP, trata-se de classificar a dificuldade das mesmas instâncias.
Há muita bibliografia sobre o efeito conhecido como transição de fase . Em particular, no caso de fórmulas aleatórias de 3-SAT na Forma Normal Conjuntiva (CNF), sabe-se que existe um valor R da razão de cláusulas para variáveis de modo que, para todos os r <R, a fórmula possa ser satisfeita com alta probabilidade e para r> R a fórmula é insatisfatória com alta probabilidade. O efeito de transição de fase ocorre próximo de R e tem o efeito notável de que resolver o problema de satisfação dessas fórmulas é extremamente difícil na prática.
Como para provar a dureza NP de um determinado problema, é necessário mostrar que existe um tempo polinomial Redução de Turing de um problema NP completo e que problemas NP completos podem ser transformados em tempo polinomial entre eles; naturalmente surge a seguinte pergunta:
É possível classificar a dificuldade dos problemas difíceis de NP na prática usando a transição de fase do 3-SAT CNF como um indicador? A intuição é que se pode esperar que um problema P1 seja mais difícil que P2 se sua codificação 3-SAT estiver mais próxima de R (que é conhecido por estar próximo de 4,2). Observe que essa ideia não vincula necessariamente cada instância específica a uma dificuldade específica, apenas as classifica.
Existem vários contra-argumentos, entre eles:
- A transição de fase da fórmula 3-SAT CNF se aplica a fórmulas aleatórias. No entanto, uma instância específica em um problema diferente tem alguma estrutura que pode ser explorada pelos solucionadores para esse problema - isso já foi apontado por Peter Shor na pergunta acima mencionada.
- Pode ser que a codificação específica usada para transformar as instâncias particulares em nosso problema para 3-SAT desempenhe um papel crucial na proporção de cláusulas para variáveis que levam a valores enganosos, portanto, classificações errôneas --- essa preocupação é levantada por Kaveh em os comentários a esta pergunta.
- Serge (de acordo com meu entendimento de seu comentário a essa pergunta) levanta a questão de que se pode complicar artificialmente o problema difícil de NP original, de modo que ele resulte em uma fórmula 3CNF que altera a proporção de cláusulas em relação a variáveis, preservando a satisfação.
Quanto a 1, todos os problemas podem compartilhar a mesma classe de regularidade, para que problemas de classificação (em vez de caracterizar a dificuldade) possam ser aplicados; quanto a 2, existem codificações em problemas específicos que são conhecidos como não redundantes, de acordo com a regra de Propagação da Unidade, de modo que essas devem ser preferidas e talvez elas evitem essas classificações errôneas. Um exemplo é Sideris et al., 2010, para o caso do Planejamento Proposicional. Quanto a 3, Cheeseman et al., 1991 já consideravam a questão de saber se os mapeamentos entre problemas preservam ou não o efeito de transição de fase e seus experimentos preliminares parecem apoiar sua conjectura, desde que se reduza o problema original de PN e até que " possa ser ainda mais reduzido aplicando resolução às cláusulas ".
Tudo isso faz sentido para você? você tem conhecimento de alguma referência bibliográfica sobre isso? Qualquer orientação seria amplamente reconhecida!
fonte
Respostas:
Embora não seja inconcebível que os obstáculos técnicos que você mencione possam ser superados de alguma forma, acho que atualmente há muito pouca motivação para fazê-lo, pela simples razão de que (pelo menos tanto quanto eu sei) a dificuldade do NP-hard problemas na prática parecem, empiricamente, ter pouco a ver com sua proximidade com a transição da fase 3-SAT.
Compare isso com outras maneiras de classificar os problemas de NP-hard em termos de dificuldade: existe alguma correlação empírica entre problemas de NP-hard que são fáceis na prática e problemas de NP-hard que são fáceis de aproximar ou que são tratáveis por parâmetros fixos (no sentido de complexidade parametrizada). Noções apropriadas de redução foram desenvolvidas nesses casos que explicam parcialmente as observações empíricas. No entanto, atualmente, parece não haver indicação empírica de que a maioria dos problemas difíceis de NP difíceis na prática sejam difíceis devido à sua estreita relação com instâncias de 3-SAT perto da transição de fase. Portanto, não faz muito sentido desenvolver uma teoria para "explicar" algo que não parece ser verdade na prática.
fonte