SNP (complexity) (original) (raw)
In computational complexity theory, SNP (from Strict NP) is a complexity class containing a limited subset of NP based on its logical characterization in terms of graph-theoretical properties. It forms the basis for the definition of the class MaxSNP of optimization problems. It is defined as the class of problems that are properties of relational structures (such as graphs) expressible by a second-order logic formula of the following form: , .
| Property | Value |
|---|---|
| dbo:abstract | In computational complexity theory, SNP (from Strict NP) is a complexity class containing a limited subset of NP based on its logical characterization in terms of graph-theoretical properties. It forms the basis for the definition of the class MaxSNP of optimization problems. It is defined as the class of problems that are properties of relational structures (such as graphs) expressible by a second-order logic formula of the following form: , where are relations of the structure (such as the adjacency relation, for a graph), are unknown relations (sets of tuples of vertices), and is a quantifier-free formula: any boolean combination of the relations. That is, only existential second-order quantification (over relations) is allowed and only universal first-order quantification (over vertices) is allowed.If existential quantification over vertices were also allowed, the resulting complexity class would be equal to NP (more precisely, the class of those properties of relational structures that are in NP), a fact known as Fagin's theorem. For example, SNP contains 3-Coloring (the problem of determining whether a given graph is 3-colorable), because it can be expressed by the following formula: . Here denotes the adjacency relation of the input graph, while the sets (unary relations) correspond to sets of vertices colored with one of the 3 colors.Similarly, SNP contains the k-SAT problem: the boolean satisfiability problem (SAT) where the formula is restricted to conjunctive normal form and to at most k literals per clause, where k is fixed. (en) 계산 복잡도 이론에서 MAX-SNP는 최적화 문제의 근사 가능성에 대한 복잡도 종류이다. 는 Strict NP를 줄인 말이다. 엄격한(strict)이라는 말이 앞에 붙은 이유는 MAX-SNP가 NP에 대한 약한 (weak verifier)와 관련되기 때문이다. MAX-SNP 문제는 MAX-SNP0이라는 문제로 L-환산(L-reduction)이 되는 최적화 문제의 집합이다. L-환산이란 NP-난해를 증명할 때 쓰는 다항 시간 환산과 달리 근사 가능성까지 보존하는 환산이다. 따라서 MAX-SNP는 MAX-SNP0과 근사 가능성이 같은 문제의 집합이라고 볼 수 있다. 뒤에 나오는 결과를 써서 정리하면 이것은 최적해의 상수배 이내로 근사가 가능한 문제의 집합과 같다. 다른 복잡도 종류와 비슷하게 과 복잡도 종류도 정의할 수 있다. NP-완전이 다항 시간에 풀리지 않을 것으로 예상되는 문제의 집합인 것과 비슷하게, MAX-SNP-완전 문제는 PTAS를 가지지 않을 것으로 예상되는 문제의 집합이다. 만약 MAX-SNP-난해 문제 중 하나라도 PTAS를 가지면 다른 모든 MAX-SNP-난해 문제가 PTAS를 가질 뿐만 아니라 P=NP까지 성립하게 된다. 현재 학계에서는 P와 NP는 다르다고 보고 있으므로, MAX-SNP-난해 문제 역시 PTAS를 가지지 않을 것으로 본다. 어떤 문제가 MAX-SNP-완전인지 아닌지는 주로 기본 문제인 으로 L-환산을 해서 증명한다. 이는 NP-완전을 증명할 때 충족 가능성 문제로 다항 시간 환산을 하는 것과 비슷하다. (ko) Na teoria da complexidade computacional, SNP (de Strict NP) é uma classe de complexidade que contém um subconjunto limitado de NP baseado em sua caracterização lógica em termos de propriedades da Teoria dos grafos. Ela forma a base para a definição da classe MaxSNP de problemas de otimização. Uma caracterização da Classe de complexidade NP, como mostrado por Ronald Fagin em 1974 e relacionada ao Teorema de Fagin, é que é o conjunto de problemas que podem ser reduzidos a propriedades de grafos que podem ser expressas em Lógica de segunda ordem existencial. Esta lógica permite quantificação universal (∀) e existencial (∃) sobre vértices, mas apenas quantificação existencial sobre conjuntos de vértices e relações entre os vértices. SNP retém quantificação existencial sobre conjuntos e relações, mas apenas permite quantificação universal sobre vértices. SNP contém k-SAT, o Problema de satisfatibilidade booleana (SAT), onde a fórmula é restrita a forma normal conjuntiva e, no máximo, k literais por cláusula, onde k é fixo. (pt) |
| dbo:wikiPageExternalLink | https://archive.org/details/finitemodeltheor00grde https://archive.org/details/finitemodeltheor00grde/page/n358 |
| dbo:wikiPageID | 13270149 (xsd:integer) |
| dbo:wikiPageLength | 5659 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1100495667 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:NP_(complexity) dbr:MAX-3SAT dbr:Approximation-preserving_reduction dbr:Approximation_algorithm dbr:L-reduction dbr:Graph_(discrete_mathematics) dbr:Graph_coloring dbr:Conjunctive_normal_form dbr:Complete_(complexity) dbr:Complexity_class dbr:Computational_complexity_theory dbr:PCP_theorem dbr:PTAS_reduction dbr:Graph_theory dbc:Complexity_classes dbr:APX dbr:Boolean_satisfiability_problem dbr:MaxSNP dbr:Optimization_problem dbr:Second-order_logic dbr:Fagin's_theorem dbr:Springer-Verlag dbr:Relational_structure |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Reflist dbt:CZoo |
| dct:subject | dbc:Complexity_classes |
| gold:hypernym | dbr:Class |
| rdf:type | yago:WikicatComplexityClasses yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Group100031264 |
| rdfs:comment | In computational complexity theory, SNP (from Strict NP) is a complexity class containing a limited subset of NP based on its logical characterization in terms of graph-theoretical properties. It forms the basis for the definition of the class MaxSNP of optimization problems. It is defined as the class of problems that are properties of relational structures (such as graphs) expressible by a second-order logic formula of the following form: , . (en) 계산 복잡도 이론에서 MAX-SNP는 최적화 문제의 근사 가능성에 대한 복잡도 종류이다. 는 Strict NP를 줄인 말이다. 엄격한(strict)이라는 말이 앞에 붙은 이유는 MAX-SNP가 NP에 대한 약한 (weak verifier)와 관련되기 때문이다. MAX-SNP 문제는 MAX-SNP0이라는 문제로 L-환산(L-reduction)이 되는 최적화 문제의 집합이다. L-환산이란 NP-난해를 증명할 때 쓰는 다항 시간 환산과 달리 근사 가능성까지 보존하는 환산이다. 따라서 MAX-SNP는 MAX-SNP0과 근사 가능성이 같은 문제의 집합이라고 볼 수 있다. 뒤에 나오는 결과를 써서 정리하면 이것은 최적해의 상수배 이내로 근사가 가능한 문제의 집합과 같다. (ko) Na teoria da complexidade computacional, SNP (de Strict NP) é uma classe de complexidade que contém um subconjunto limitado de NP baseado em sua caracterização lógica em termos de propriedades da Teoria dos grafos. Ela forma a base para a definição da classe MaxSNP de problemas de otimização. SNP contém k-SAT, o Problema de satisfatibilidade booleana (SAT), onde a fórmula é restrita a forma normal conjuntiva e, no máximo, k literais por cláusula, onde k é fixo. (pt) |
| rdfs:label | MAX-SNP (ko) SNP (complexity) (en) SNP (complexidade) (pt) |
| owl:sameAs | freebase:SNP (complexity) yago-res:SNP (complexity) wikidata:SNP (complexity) dbpedia-ko:SNP (complexity) dbpedia-pt:SNP (complexity) https://global.dbpedia.org/id/fy9i |
| prov:wasDerivedFrom | wikipedia-en:SNP_(complexity)?oldid=1100495667&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:SNP_(complexity) |
| is dbo:wikiPageDisambiguates of | dbr:SNP |
| is dbo:wikiPageRedirects of | dbr:MaxSNP dbr:MAX-SNP dbr:MAXSNP dbr:Strict_NP |
| is dbo:wikiPageWikiLink of | dbr:Betweenness dbr:Cycle_basis dbr:Independent_set_(graph_theory) dbr:MaxSNP dbr:SNP dbr:Exponential_time_hypothesis dbr:Planarization dbr:Nonblocker dbr:MAX-SNP dbr:MAXSNP dbr:Strict_NP |
| is foaf:primaryTopic of | wikipedia-en:SNP_(complexity) |