Max/min CSP/Ones classification theorems
id:
max-min-csp-ones-classification-theorems-193-10188917
title:
Max/min CSP/Ones classification theorems
text:
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 solut
brand slug:
wiki
category slug:
encyclopedia
description:
On the complexity classes of problems about satisfying a subset of boolean relations
original url:
https://en.wikipedia.org/wiki/Max/min_CSP/Ones_classification_theorems
date created:
date modified:
2022-08-04T05:24:20Z
main entity:
{"identifier":"Q25048562","url":"https://www.wikidata.org/entity/Q25048562"}
image:
fields total:
13
integrity:
14