About: 2-satisfiability

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Theoretical computer science problem

Property	Value
dbo:description	problema di soddisfacibilità booleana (it) theoretical computer science problem (en) kielégíthetőségi probléma, ahol minden klóz legfeljebb két literált tartalmaz (hu)
dbo:thumbnail	wiki-commons:Special:FilePath/Implication_graph.svg?width=300
dbo:wikiPageWikiLink	dbr:Graph_drawing dbr:Backtracking dbr:Parameterized_complexity dbr:Binary_image dbr:Polyomino dbr:Implication_graph dbr:NL_(complexity) dbr:Hamming_distance dbr:Undirected_graph dbr:P_versus_NP_problem dbr:True_quantified_Boolean_formula dbr:Tarjan's_strongly_connected_components_algorithm dbr:Constraint_satisfaction_problem dbr:Immerman–Szelepcsényi_theorem dbr:Majority_function dbr:Resolution_(logic) dbr:Constraint_(mathematics) dbr:Logarithm dbr:Metric_space dbr:NP_(complexity) dbr:Identity_matrix dbr:Heuristic dbc:NL-complete_problems dbr:Independent_set_(graph_theory) dbc:Satisfiability_problems dbr:Cut_(graph_theory) dbr:Semidefinite_programming dbr:Counting_problem_(complexity) dbr:Path-based_strong_component_algorithm dbr:NL-complete dbr:Directed_graph dbr:Logical_conjunction dbr:Transitive_closure dbr:Exponential_time_hypothesis dbr:Completeness_(logic) dbr:Depth-first_search dbr:Binary_data dbr:Round-robin_tournament dbr:Directed_acyclic_graph dbr:RP_(complexity) dbr:Vertex_(graph_theory) dbr:Implicit_graph dbr:Graph_theory dbr:Limit_of_a_sequence dbr:Horn-satisfiability dbr:Computer_science dbr:Diameter dbr:Pixel dbr:Equivalence_relation dbr:University_of_California,_Davis dbr:Many-valued_logic dbr:Phase_transition dbr:Computational_complexity_theory dbr:Necessary_and_sufficient_condition dbr:Boolean_satisfiability_problem dbr:Tomography dbr:Complete_bipartite_graph dbr:Complexity_class dbr:Strongly_connected_component dbr:Median_graph dbr:Unique_games_conjecture dbr:Transitive_relation dbr:Approximation_algorithm dbr:Logical_equivalence dbr:Topological_sorting dbr:Conjunctive_normal_form dbr:Polynomial-time_approximation_scheme dbr:Boolean_expression dbr:Discrete_tomography dbr:Boolean_logic dbr:Nonogram dbr:Automatic_label_placement dbr:Computational_problem dbr:Square_lattice dbr:Literal_(mathematical_logic) dbr:Dynamic_programming dbr:Graph_automorphism dbr:Skew-symmetric_graph dbr:Davis–Putnam_algorithm dbr:Clause_(logic) dbr:Kosaraju's_algorithm dbr:VLSI dbr:NP-complete dbr:NP-hard dbr:Sharp-P-complete dbr:Polynomial_time dbr:Linear_time dbr:Arc_diagram dbr:Maximum_satisfiability_problem dbr:Strongly_connected_components dbr:Maximum_flow dbr:0-1_matrix dbr:Evolutionary_tree dbr:Existential_quantifier dbr:First_order_logic dbr:Fixed-parameter_tractable dbr:Data_clustering dbr:Orthogonal_convexity dbr:Disjunction dbr:W(1) dbr:Approximation_ratio dbr:Second_order_logic dbr:Truth_assignment dbr:Vertex_cover_problem dbr:File:2SAT_median_graph.svg dbr:File:Implication_graph.svg dbr:File:Paint_by_numbers_Animation.gif dbr:Implicative_normal_form
dbp:last	Batenburg (en) Kosters (en)
dbp:wikiPageUsesTemplate	dbt:Good_article dbt:Reflist dbt:Math dbt:Mvar dbt:Harvs dbt:Harvtxt dbt:Short_description
dbp:year	2008 (xsd:integer) 2009 (xsd:integer)
dct:subject	dbc:NL-complete_problems dbc:Satisfiability_problems
gold:hypernym	dbr:Problem
rdfs:label	2-satisfiability (en) قابلية الإرضاء الثنائية (ar) 2-satisfiability (it) Problème 2-SAT (fr)
owl:sameAs	freebase:2-satisfiability yago-res:2-satisfiability wikidata:2-satisfiability dbpedia-it:2-satisfiability dbpedia-fr:2-satisfiability dbpedia-hu:2-satisfiability dbpedia-ar:2-satisfiability dbpedia-global:2-satisfiability
prov:wasDerivedFrom	wikipedia-en:2-satisfiability?oldid=1266128791&ns=0
foaf:depiction	wiki-commons:Special:FilePath/2SAT_median_graph.svg wiki-commons:Special:FilePath/Implication_graph.svg wiki-commons:Special:FilePath/Nonogram_wiki.svg
foaf:isPrimaryTopicOf	wikipedia-en:2-satisfiability
is dbo:wikiPageRedirects of	dbr:2SAT dbr:Krom-clause dbr:Krom_formula dbr:Krom_formulae dbr:Max_2-sat dbr:Maximum_2-satisfiability dbr:2-CNF-SAT dbr:2-SAT dbr:MAX-2-SAT dbr:MAX-2SAT
is dbo:wikiPageWikiLink of	dbr:List_of_computability_and_complexity_topics dbr:Implication_graph dbr:Interval_scheduling dbr:NL_(complexity) dbr:NP-completeness dbr:True_quantified_Boolean_formula dbr:Adi_Shamir dbr:Satisfiability dbr:NL-complete dbr:Uwe_Schöning dbr:Exponential_time_hypothesis dbr:♯P-complete dbr:Birkhoff's_representation_theorem dbr:Horn-satisfiability dbr:MAXEkSAT dbr:2SAT dbr:Strongly_connected_component dbr:Median_graph dbr:Maximal_independent_set dbr:Unique_games_conjecture dbr:Conjunctive_normal_form dbr:P_(complexity) dbr:PLS_(complexity) dbr:Nonogram dbr:Automatic_label_placement dbr:Skew-symmetric_graph dbr:Gadget_(computer_science) dbr:Book_embedding dbr:Index_of_combinatorics_articles dbr:Harry_R._Lewis dbr:Arc_diagram dbr:Maximum_satisfiability_problem dbr:Krom-clause dbr:Krom_formula dbr:Krom_formulae dbr:Max_2-sat dbr:Maximum_2-satisfiability dbr:2-CNF-SAT dbr:2-SAT dbr:MAX-2-SAT dbr:MAX-2SAT
is foaf:primaryTopic of	wikipedia-en:2-satisfiability