MAX-3SAT is a problem in the computational complexity subfield of computer science. It generalises the Boolean satisfiability problem (SAT) which is a decision problem considered in complexity theory. It is defined as: Given a 3-CNF formula Φ (i.e. with at most 3 variables per clause), find an assignment that satisfies the largest number of clauses. MAX-3SAT is a canonical complete problem for the complexity class MAXSNP (shown complete in Papadimitriou pg. 314).
Attributes | Values |
---|
rdf:type
| |
rdfs:label
| - MAX-3SAT (en)
- MAX-3SAT (pt)
|
rdfs:comment
| - MAX-3SAT is a problem in the computational complexity subfield of computer science. It generalises the Boolean satisfiability problem (SAT) which is a decision problem considered in complexity theory. It is defined as: Given a 3-CNF formula Φ (i.e. with at most 3 variables per clause), find an assignment that satisfies the largest number of clauses. MAX-3SAT is a canonical complete problem for the complexity class MAXSNP (shown complete in Papadimitriou pg. 314). (en)
- MAX-3SAT é um problema em complexidade computacional, uma subárea da ciência da computação. Este problema generaliza o (SAT), que é um problema de decisão dentro da teoria da complexidade. E é definido como: Dada uma 3-CNF formula Φ (i.e. com no máximo 3 variáveis por cláusula), ache uma atribuição que satisfaz o maior número de cláusulas. MAX-3SAT é um problema canônico completo da classe de complexidade MAXSNP (ver Papadimitriou pg. 314). (pt)
|
dcterms:subject
| |
Wikipage page ID
| |
Wikipage revision ID
| |
Link from a Wikipage to another Wikipage
| |
Link from a Wikipage to an external page
| |
sameAs
| |
dbp:wikiPageUsesTemplate
| |
has abstract
| - MAX-3SAT is a problem in the computational complexity subfield of computer science. It generalises the Boolean satisfiability problem (SAT) which is a decision problem considered in complexity theory. It is defined as: Given a 3-CNF formula Φ (i.e. with at most 3 variables per clause), find an assignment that satisfies the largest number of clauses. MAX-3SAT is a canonical complete problem for the complexity class MAXSNP (shown complete in Papadimitriou pg. 314). (en)
- MAX-3SAT é um problema em complexidade computacional, uma subárea da ciência da computação. Este problema generaliza o (SAT), que é um problema de decisão dentro da teoria da complexidade. E é definido como: Dada uma 3-CNF formula Φ (i.e. com no máximo 3 variáveis por cláusula), ache uma atribuição que satisfaz o maior número de cláusulas. MAX-3SAT é um problema canônico completo da classe de complexidade MAXSNP (ver Papadimitriou pg. 314). (pt)
|
gold:hypernym
| |
prov:wasDerivedFrom
| |
page length (characters) of wiki page
| |
foaf:isPrimaryTopicOf
| |
is Link from a Wikipage to another Wikipage
of | |
is Wikipage redirect
of | |
is foaf:primaryTopic
of | |