What is the computational complexity of the 2-satisfiability problem? (Q281): Difference between revisions

Latest revision as of 23:37, 12 March 2026

No description defined

What is the complexity of 2SAT?
What is the complexity class of 2-SAT?

Language	Label	Description	Also known as
English	What is the computational complexity of the 2-satisfiability problem?	No description defined	What is the complexity of 2SAT? What is the complexity class of 2-SAT?

Statements

instance of

question

0 references

query

SELECT ?obj WHERE { wd:Q4596967 wdt:P10374 ?obj . }

0 references

computational complexity (English)

0 references

computational (English)

Wikidata item ID

Q12525525

Q622821

0 references

2-satisfiability problem (English)

Wikidata item ID

Q4596967

0 references

2-satisfiability (English)

Wikidata item ID

Q4596967

0 references

complexity (English)

0 references

2SAT (English)

Wikidata item ID

Q4596967

0 references

complexity class (English)

Wikidata item ID

Q908207

0 references

class (English)

Wikidata item ID

Q217594

0 references

2-SAT (English)

Wikidata item ID

Q4596967

0 references

complejidad computacional (Spanish)

0 references

problema de 2-satisfactibilidad (Spanish)

Wikidata item ID

Q4596967

0 references

2-satisfactibilidad (Spanish)

Wikidata item ID

Q4596967

0 references

problem (English)

Wikidata item ID

Q3435924

0 references

problema (Spanish)

Wikidata item ID

Q3435924

0 references

complejidad (Spanish)

0 references

computacional (Spanish)

Wikidata item ID

Q12525525

Q622821

0 references

2SAT (Spanish)

Wikidata item ID

Q4596967

0 references

clase de complejidad (Spanish)

Wikidata item ID

Q908207

0 references

clase (Spanish)

Wikidata item ID

Q217594

0 references

2-SAT (Spanish)

Wikidata item ID

Q4596967

0 references

@@ aliases / es / 0 / aliases / es / 0 @@
+¿Qué complejidad tiene 2SAT?
@@ aliases / es / 1 / aliases / es / 1 @@
+¿En qué clase de complejidad está 2-SAT?
@@ Property / instance of @@
+question
@@ Property / instance of: question / rank @@
+Normal rank
@@ Property / query @@
+SELECT ?obj WHERE { wd:Q4596967 wdt:P10374 ?obj . }
@@ Property / query: SELECT ?obj WHERE { wd:Q4596967 wdt:P10374 ?obj . } / rank @@
+Normal rank
+dataset: Wikidata
+query language: SPARQL
@@ Property / mention @@
+computational complexity (English)
@@ Property / mention: computational complexity (English) / rank @@
+Normal rank
@@ Property / mention: computational complexity (English) / qualifier @@
+Wikidata item ID: Q5157286
@@ Property / mention: computational complexity (English) / qualifier @@
+Wikidata property ID: P10374
@@ Property / mention @@
+computational (English)
@@ Property / mention: computational (English) / rank @@
+Normal rank
@@ Property / mention: computational (English) / qualifier @@
+Wikidata item ID: Q12525525
@@ Property / mention: computational (English) / qualifier @@
+Wikidata item ID: Q622821
@@ Property / mention @@
+-satisfiability problem (English)
@@ Property / mention: 2-satisfiability problem (English) / rank @@
+Normal rank
@@ Property / mention: 2-satisfiability problem (English) / qualifier @@
+Wikidata item ID: Q4596967
@@ Property / mention @@
+-satisfiability (English)
@@ Property / mention: 2-satisfiability (English) / rank @@
+Normal rank
@@ Property / mention: 2-satisfiability (English) / qualifier @@
+Wikidata item ID: Q4596967
@@ Property / mention @@
+complexity (English)
@@ Property / mention: complexity (English) / rank @@
+Normal rank
@@ Property / mention: complexity (English) / qualifier @@
+Wikidata item ID: Q5157286
@@ Property / mention: complexity (English) / qualifier @@
+Wikidata property ID: P10374
@@ Property / mention @@
+SAT (English)
@@ Property / mention: 2SAT (English) / rank @@
+Normal rank
@@ Property / mention: 2SAT (English) / qualifier @@
+Wikidata item ID: Q4596967
@@ Property / mention @@
+complexity class (English)
@@ Property / mention: complexity class (English) / rank @@
+Normal rank
@@ Property / mention: complexity class (English) / qualifier @@
+Wikidata item ID: Q908207
@@ Property / mention @@
+class (English)
@@ Property / mention: class (English) / rank @@
+Normal rank
@@ Property / mention: class (English) / qualifier @@
+Wikidata item ID: Q217594
@@ Property / mention @@
+-SAT (English)
@@ Property / mention: 2-SAT (English) / rank @@
+Normal rank
@@ Property / mention: 2-SAT (English) / qualifier @@
+Wikidata item ID: Q4596967
@@ Property / mention @@
+complejidad computacional (Spanish)
@@ Property / mention: complejidad computacional (Spanish) / rank @@
+Normal rank
@@ Property / mention: complejidad computacional (Spanish) / qualifier @@
+Wikidata item ID: Q5157286
@@ Property / mention: complejidad computacional (Spanish) / qualifier @@
+Wikidata property ID: P10374
@@ Property / mention @@
+problema de 2-satisfactibilidad (Spanish)
@@ Property / mention: problema de 2-satisfactibilidad (Spanish) / rank @@
+Normal rank
@@ Property / mention: problema de 2-satisfactibilidad (Spanish) / qualifier @@
+Wikidata item ID: Q4596967
@@ Property / mention @@
+-satisfactibilidad (Spanish)
@@ Property / mention: 2-satisfactibilidad (Spanish) / rank @@
+Normal rank
@@ Property / mention: 2-satisfactibilidad (Spanish) / qualifier @@
+Wikidata item ID: Q4596967
@@ Property / mention @@
+problem (English)
@@ Property / mention: problem (English) / rank @@
+Normal rank
@@ Property / mention: problem (English) / qualifier @@
+Wikidata item ID: Q3435924
@@ Property / mention @@
+problema (Spanish)
@@ Property / mention: problema (Spanish) / rank @@
+Normal rank
@@ Property / mention: problema (Spanish) / qualifier @@
+Wikidata item ID: Q3435924
@@ Property / mention @@
+complejidad (Spanish)
@@ Property / mention: complejidad (Spanish) / rank @@
+Normal rank
@@ Property / mention: complejidad (Spanish) / qualifier @@
+Wikidata item ID: Q5157286
@@ Property / mention: complejidad (Spanish) / qualifier @@
+Wikidata property ID: P10374
@@ Property / mention @@
+computacional (Spanish)
@@ Property / mention: computacional (Spanish) / rank @@
+Normal rank
@@ Property / mention: computacional (Spanish) / qualifier @@
+Wikidata item ID: Q12525525
@@ Property / mention: computacional (Spanish) / qualifier @@
+Wikidata item ID: Q622821
@@ Property / mention @@
+SAT (Spanish)
@@ Property / mention: 2SAT (Spanish) / rank @@
+Normal rank
@@ Property / mention: 2SAT (Spanish) / qualifier @@
+Wikidata item ID: Q4596967
@@ Property / mention @@
+clase de complejidad (Spanish)
@@ Property / mention: clase de complejidad (Spanish) / rank @@
+Normal rank
@@ Property / mention: clase de complejidad (Spanish) / qualifier @@
+Wikidata item ID: Q908207
@@ Property / mention @@
+clase (Spanish)
@@ Property / mention: clase (Spanish) / rank @@
+Normal rank
@@ Property / mention: clase (Spanish) / qualifier @@
+Wikidata item ID: Q217594
@@ Property / mention @@
+-SAT (Spanish)
@@ Property / mention: 2-SAT (Spanish) / rank @@
+Normal rank
@@ Property / mention: 2-SAT (Spanish) / qualifier @@
+Wikidata item ID: Q4596967