About: 2-satisfiability   Goto Sponge  NotDistinct  Permalink

An Entity of Type : yago:Problem114410605, within Data Space : wasabi.inria.fr associated with source document(s)

In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables. It is a special case of the general Boolean satisfiability problem, which can involve constraints on more than two variables, and of constraint satisfaction problems, which can allow more than two choices for the value of each variable. But in contrast to those more general problems, which are NP-complete, 2-satisfiability can be solved in polynomial time.

AttributesValues
type
label
  • 2-satisfiability
  • 2-satisfiability
  • Problème 2-SAT
  • قابلية الإرضاء الثنائية
comment
  • En informatique théorique, le problème 2-SAT est un problème de décision. C'est une restriction du problème SAT qui peut être résolu en temps polynomial, alors que le problème général est NP complet. Le problème 2-SAT consiste à décider si une formule booléenne en forme normale conjonctive, dont toutes les clauses sont de taille 2, est satisfaisable. De telles formules sont appelées 2-CNF ou formules de Krom.
  • تعرّف قابلية الإرضاء الثنائية، 2-إس إيه تي، في علوم الحاسوب، بأنها مسألة حاسوبية لتعيين قيم لمتغيرات، لكل منها قيمتان محتملتان، لإرضاء نظام القيود على أزواج المتغيرات. وتعد حالة خاصة من مسألة قابلية الإرضاء المنطقية العامة، التي يمكن أن تتضمن قيودًا على أكثر من متغيرين، ومن مسألة إرضاء القيد، التي يمكن أن تسمح بأكثر من خيارين لقيمة كل متغير. ولكن على عكس هذه المسائل الأكثر عمومية، التي تعد مسائل كثيرة حدود غير قطعية كاملة، يمكن حل قابلية الإرضاء الثنائية في زمن متعدد الحدود.
  • In informatica, 2-satisfiability, 2-SAT o semplicemente 2SAT è un problema di soddisfacibilità booleana con clausole composte da coppie di letterali. È un caso particolare (il più semplice) del problema n-SAT, ed è l'unico di cui è stata dimostrata la risolubilità in tempo polinomiale e spazio logaritmico. Più precisamente, si tratta di un problema . Al contrario, i problemi di soddisfacibilità con sono tutti NP-completi, essendo tali sia il generico SAT (per il teorema di Cook) che 3-SAT (poiché ogni problema n-SAT è riducibile a 3-SAT in tempo polinomiale).
  • In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables. It is a special case of the general Boolean satisfiability problem, which can involve constraints on more than two variables, and of constraint satisfaction problems, which can allow more than two choices for the value of each variable. But in contrast to those more general problems, which are NP-complete, 2-satisfiability can be solved in polynomial time.
sameAs
topic
depiction
  • External Image
  • External Image
  • External Image
described by
Subject
dbo:wikiPageID
dbo:wikiPageRevisionID
dbo:wikiPageWikiLink
Faceted Search & Find service v1.13.91 as of Mar 24 2020


Alternative Linked Data Documents: Sponger | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data]
OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software