MAX-3LIN-EQN - MAX-3LIN-EQN

MAX-3LIN-EQN je problém v Teorie výpočetní složitosti kde vstupem je soustava lineárních rovnic (modulo 2). Každá rovnice obsahuje nejvýše 3 proměnné. Problémem je najít přiřazení k proměnným, které splňuje maximální počet rovnic.

Tento problém úzce souvisí s MAX-3SAT problém. to je NP-tvrdé přiblížit MAX-3LIN-EQN s poměrem (1/2 - δ) pro libovolný δ> 0.

Viz také

• PCP (složitost)

Reference

• Rudich a kol., „Teorie výpočetní složitosti“

IAS / Park City Mathematics Series, 2004, strana 108ISBN  0-8218-2872-X

• J. Hastad. „Nějaké optimální výsledky nepřibližnosti.“

V sborníku z 29. ACM STOC, 1. – 10. 1997