MAX-3LIN-EQN

MAX-3LIN-EQN to problem w teorii złożoności obliczeniowej , w którym danymi wejściowymi jest układ równań liniowych (modulo 2). Każde równanie zawiera co najwyżej 3 zmienne. Problem polega na znalezieniu przypisania do zmiennych, które spełnia maksymalną liczbę równań.

Ten problem jest ściśle powiązany z problemem MAX-3SAT . Jest NP-trudne przybliżenie MAX-3LIN-EQN ze stosunkiem (1/2 - δ) dla dowolnego δ > 0.

Zobacz też

  • Rudich i in., „Teoria złożoności obliczeniowej”,

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

  • J.Hastad. „Niektóre optymalne wyniki nieprzybliżenia”.

W obradach 29 ACM STOC, 1-10, 1997

Pobrano z „ https://en.wikipedia.org/w/index.php?title=MAX-3LIN-EQN&oldid=789050365 ”