| dbo:abstract
|
- In computational complexity theory, a branch of computer science, the Max/min CSP/Ones classification theorems state necessary and sufficient conditions that determine the complexity classes of problems about satisfying a subset S of boolean relations. They are similar to Schaefer's dichotomy theorem, which classifies the complexity of satisfying finite sets of relations; however, the Max/min CSP/Ones classification theorems give information about the complexity of approximating an optimal solution to a problem defined by S. Given a set S of clauses, the Max constraint satisfaction problem (CSP) is to find the maximum number (in the weighted case: the maximal sum of weights) of satisfiable clauses in S. Similarly, the Min CSP problem is to minimize the number of unsatisfied clauses. The Max Ones problem is to maximize the number of boolean variables in S that are set to 1 under the restriction that all clauses are satisfied, and the Min Ones problem is to minimize this number. When using the classifications below, the problem's complexity class is determined by the topmost classification that it satisfies. (en)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 7422 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdfs:comment
|
- In computational complexity theory, a branch of computer science, the Max/min CSP/Ones classification theorems state necessary and sufficient conditions that determine the complexity classes of problems about satisfying a subset S of boolean relations. They are similar to Schaefer's dichotomy theorem, which classifies the complexity of satisfying finite sets of relations; however, the Max/min CSP/Ones classification theorems give information about the complexity of approximating an optimal solution to a problem defined by S. (en)
|
| rdfs:label
|
- Max/min CSP/Ones classification theorems (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
