MAXEkSAT
id:
maxeksat-237-7595546
title:
MAXEkSAT
text:
MAXEkSAT is a problem in computational complexity theory that is a maximization version of the Boolean satisfiability problem 3SAT. In MAXEkSAT, each clause has exactly k literals, each with distinct variables, and is in conjunctive normal form. These are called k-CNF formulas. The problem is to determine the maximum number of clauses that can be satisfied by a truth assignment to the variables in the clauses. We say that an algorithm A provides an α-approximation to MAXEkSAT if, for some fixed
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/MAXEkSAT
date created:
date modified:
2024-04-17T21:11:52Z
main entity:
{"identifier":"Q6714607","url":"https://www.wikidata.org/entity/Q6714607"}
image:
fields total:
13
integrity:
13