Search strategies and phase transition in the Random Boolean satisfiability problem (2021)
- Authors:
- Autor USP: BITTENCOURT, HEITOR PASCOAL DE - IFSC
- Unidade: IFSC
- Sigla do Departamento: FCI
- DOI: 10.11606/D.76.2021.tde-02092021-162034
- Subjects: ALGORITMOS; MUDANÇA DE FASE
- Keywords: Algoritmos de busca local; Boolean satisfiability problem; Local search algorithms; NP-complete problem; Phase transitions; Problema de satisfatibilidade booliana; Problema NP-completo; Problemas aleatórios; Random problems; Transição de fase
- Agências de fomento:
- Language: Inglês
- Abstract: O problema da satisfatibilidade booliana é o problema de decidir se uma determinada fórmula booliana, como (x1 ∨ x2 ∨ ¬x3) ∧ (¬x1) ∧ (x2 ∨ x3) é satisfatível, ou seja, se há uma atribuição de True ou False às variáveis lógicas x1, x2 e x3 de modo que a fórmula seja avaliada como True. Este foi o primeiro problema provado ser NP-completo, o que significa que não há algoritmo conhecido que pode resolvê-lo com um tempo de execução que escale polinomialmente com o tamanho do problema em um cenário de pior caso. Nessa dissertação, estudamos fórmulas boolianas aleatórias com número fixo de variáveis N e número de cláusulas M que são geradas escolhendo aleatoriamente as variáveis que aparecem em cada cláusula e negando-as com probabilidade 1/2. Resolvemos essas fórmulas usando um algoritmo de busca local baseado em passeio aleatório conhecido como WalkSAT. Mostramos que o WalkSAT pode ser usado para estudar uma propriedade notável do conjunto de fórmulas boolianas aleatórias – há um valor crítico da razão entre cláusulas e variáveis M/N que separa as fórmulas satisfatíveis das insatisfatíveis no limite de N grande – e caracterizamos a região crítica, ou a agudeza da transição, para N finito usando a teoria de escala de tamanho finito. Do ponto de vista da ciência da computação, essa transição é importante porque fórmulas aleatórias satisfatíveis com a razão M/N perto do ponto de transição são difíceis de resolver, no sentido que o WalkSAT requermuito mais tempo para encontrar suas soluções do que no caso em essa razão está longe da região crítica. Mostramos que uma estratégia de busca coletiva onde vários WalkSATs rodam em paralelo e param quando um deles encontra a solução resulta em um aumento sublinear da velocidade da busca, ou seja, o aumento de velocidade é menor do que o número de WalkSATs usados na busca coletiva
- Imprenta:
- Publisher place: São Carlos
- Date published: 2021
- Data da defesa: 08.03.2021
- Este periódico é de acesso aberto
- Este artigo NÃO é de acesso aberto
-
ABNT
BITTENCOURT, Heitor Pascoal de. Search strategies and phase transition in the Random Boolean satisfiability problem. 2021. Dissertação (Mestrado) – Universidade de São Paulo, São Carlos, 2021. Disponível em: https://www.teses.usp.br/teses/disponiveis/76/76134/tde-02092021-162034/. Acesso em: 28 fev. 2026. -
APA
Bittencourt, H. P. de. (2021). Search strategies and phase transition in the Random Boolean satisfiability problem (Dissertação (Mestrado). Universidade de São Paulo, São Carlos. Recuperado de https://www.teses.usp.br/teses/disponiveis/76/76134/tde-02092021-162034/ -
NLM
Bittencourt HP de. Search strategies and phase transition in the Random Boolean satisfiability problem [Internet]. 2021 ;[citado 2026 fev. 28 ] Available from: https://www.teses.usp.br/teses/disponiveis/76/76134/tde-02092021-162034/ -
Vancouver
Bittencourt HP de. Search strategies and phase transition in the Random Boolean satisfiability problem [Internet]. 2021 ;[citado 2026 fev. 28 ] Available from: https://www.teses.usp.br/teses/disponiveis/76/76134/tde-02092021-162034/
Informações sobre o DOI: 10.11606/D.76.2021.tde-02092021-162034 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
