{"entities":{"Q281":{"pageid":330,"ns":120,"title":"Item:Q281","lastrevid":15604,"modified":"2026-03-12T23:37:34Z","type":"item","id":"Q281","labels":{"en":{"language":"en","value":"What is the computational complexity of the 2-satisfiability problem?"},"es":{"language":"es","value":"\u00bfCu\u00e1l es la complejidad computacional del problema de 2-satisfactibilidad?"}},"descriptions":{},"aliases":{"en":[{"language":"en","value":"What is the complexity of 2SAT?"},{"language":"en","value":"What is the complexity class of 2-SAT?"}],"es":[{"language":"es","value":"\u00bfQu\u00e9 complejidad tiene 2SAT?"},{"language":"es","value":"\u00bfEn qu\u00e9 clase de complejidad est\u00e1 2-SAT?"}]},"claims":{"P1":[{"mainsnak":{"snaktype":"value","property":"P1","hash":"4fca852915edcd32a484898d3ac6774b7b253272","datavalue":{"value":{"entity-type":"item","numeric-id":1,"id":"Q1"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q281$1472751e-40bf-0f79-22f3-fc6fba306229","rank":"normal"}],"P11":[{"mainsnak":{"snaktype":"value","property":"P11","hash":"305e8c5b1bf59053b92e0eb52f34396ec85e422d","datavalue":{"value":"SELECT ?obj WHERE { wd:Q4596967 wdt:P10374 ?obj . }","type":"string"},"datatype":"string"},"type":"statement","qualifiers":{"P13":[{"snaktype":"value","property":"P13","hash":"3e79c7da9831ab25e2f8cbb49395c904b8fd71ee","datavalue":{"value":{"entity-type":"item","numeric-id":12,"id":"Q12"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}],"P12":[{"snaktype":"value","property":"P12","hash":"b768ad78c7cf159d220205294c684bb20245a982","datavalue":{"value":{"entity-type":"item","numeric-id":13,"id":"Q13"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P13","P12"],"id":"Q281$e0680937-484f-c2b4-8994-e7db60bc7030","rank":"normal"}],"P38":[{"mainsnak":{"snaktype":"value","property":"P38","hash":"52d28405a6a4328e0e2a66d96f6e687e102492de","datavalue":{"value":{"text":"computational complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","qualifiers":{"P17":[{"snaktype":"value","property":"P17","hash":"72174a1b62553b1484260ebeb4274034249c7ce5","datavalue":{"value":"Q5157286","type":"string"},"datatype":"external-id"}],"P18":[{"snaktype":"value","property":"P18","hash":"4ca1ace4c0f35111b18c9cb37dabc6752c091edf","datavalue":{"value":"P10374","type":"string"},"datatype":"external-id"}]},"qualifiers-order":["P17","P18"],"id":"Q281$a3805ad8-46eb-1f92-8bc5-8d43c4988360","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P38","hash":"88b9d2432af97b22fca5d68bd73ca335b489a6c5","datavalue":{"value":{"text":"computational","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","qualifiers":{"P17":[{"snaktype":"value","property":"P17","hash":"1d615abddd4982b181b5a699fde465f83f8698c2","datavalue":{"value":"Q12525525","type":"string"},"datatype":"external-id"},{"snaktype":"value","property":"P17","hash":"b811ce4e70f284f741d2942f01afb42af892000f","datavalue":{"value":"Q622821","type":"string"},"datatype":"external-id"}]},"qualifiers-order":["P17"],"id":"Q281$3e604927-4c45-57f7-8f7c-bd7fe6e8610e","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P38","hash":"25e3b269cc2402b5d7f5c2f1b01a7888aecdf8f5","datavalue":{"value":{"text":"2-satisfiability problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","qualifiers":{"P17":[{"snaktype":"value","property":"P17","hash":"6916893593b90dd0c3f5ed6f46b3b1bbc7e8a7b0","datavalue":{"value":"Q4596967","type":"string"},"datatype":"external-id"}]},"qualifiers-order":["P17"],"id":"Q281$7fe14bf7-4c86-790f-1b16-8ef50553dd89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P38","hash":"dcc9e560c640c5a77d05b164e59c1a1b3bd12d72","datavalue":{"value":{"text":"2-satisfiability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","qualifiers":{"P17":[{"snaktype":"value","property":"P17","hash":"6916893593b90dd0c3f5ed6f46b3b1bbc7e8a7b0","datavalue":{"value":"Q4596967","type":"string"},"datatype":"external-id"}]},"qualifiers-order":["P17"],"id":"Q281$a911b49a-4119-3b65-994d-c077a01ce487","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P38","hash":"44e496b27ab888d40c930e3b7cd19851b895b492","datavalue":{"value":{"text":"complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","qualifiers":{"P17":[{"snaktype":"value","property":"P17","hash":"72174a1b62553b1484260ebeb4274034249c7ce5","datavalue":{"value":"Q5157286","type":"string"},"datatype":"external-id"}],"P18":[{"snaktype":"value","property":"P18","hash":"4ca1ace4c0f35111b18c9cb37dabc6752c091edf","datavalue":{"value":"P10374","type":"string"},"datatype":"external-id"}]},"qualifiers-order":["P17","P18"],"id":"Q281$6338da8d-41a9-6cf6-656d-430298eb0a99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P38","hash":"4d024a60c0add11d7e1d1118bb9ec86c6ef740b7","datavalue":{"value":{"text":"2SAT","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","qualifiers":{"P17":[{"snaktype":"value","property":"P17","hash":"6916893593b90dd0c3f5ed6f46b3b1bbc7e8a7b0","datavalue":{"value":"Q4596967","type":"string"},"datatype":"external-id"}]},"qualifiers-order":["P17"],"id":"Q281$a2b5bb3f-420a-c6a5-292f-aa3505cee633","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P38","hash":"84b53beb33bdc4d7628840113043bd157b86828a","datavalue":{"value":{"text":"complexity class","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","qualifiers":{"P17":[{"snaktype":"value","property":"P17","hash":"cce300b1c6d2dfdb186b91e8616ddb14f118fdd4","datavalue":{"value":"Q908207","type":"string"},"datatype":"external-id"}]},"qualifiers-order":["P17"],"id":"Q281$111cf0c3-4b92-cea7-b905-6f3c89f74167","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P38","hash":"0716b121c55eb213e1c1ff14be10ef94ca991599","datavalue":{"value":{"text":"class","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","qualifiers":{"P17":[{"snaktype":"value","property":"P17","hash":"7f0b3bd2e40de28f1afa25a6e090d4cd65c37670","datavalue":{"value":"Q217594","type":"string"},"datatype":"external-id"}]},"qualifiers-order":["P17"],"id":"Q281$edbff3cf-47af-3d99-0284-fd0c12e5cca0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P38","hash":"b1bcbc2470a42cba35c0981944a260ccf3400eda","datavalue":{"value":{"text":"2-SAT","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","qualifiers":{"P17":[{"snaktype":"value","property":"P17","hash":"6916893593b90dd0c3f5ed6f46b3b1bbc7e8a7b0","datavalue":{"value":"Q4596967","type":"string"},"datatype":"external-id"}]},"qualifiers-order":["P17"],"id":"Q281$b2d98e3d-4c3f-92e9-cd49-eed001e31b06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P38","hash":"6e2680317bfb1a3c5ed563a2008d9aa21627a8e2","datavalue":{"value":{"text":"complejidad computacional","language":"es"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","qualifiers":{"P17":[{"snaktype":"value","property":"P17","hash":"72174a1b62553b1484260ebeb4274034249c7ce5","datavalue":{"value":"Q5157286","type":"string"},"datatype":"external-id"}],"P18":[{"snaktype":"value","property":"P18","hash":"4ca1ace4c0f35111b18c9cb37dabc6752c091edf","datavalue":{"value":"P10374","type":"string"},"datatype":"external-id"}]},"qualifiers-order":["P17","P18"],"id":"Q281$e3c35c89-4ca0-c113-3fd1-2fccd38a64bb","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P38","hash":"0fc4877d47490c817780321a14eb9cf577dc3831","datavalue":{"value":{"text":"problema de 2-satisfactibilidad","language":"es"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","qualifiers":{"P17":[{"snaktype":"value","property":"P17","hash":"6916893593b90dd0c3f5ed6f46b3b1bbc7e8a7b0","datavalue":{"value":"Q4596967","type":"string"},"datatype":"external-id"}]},"qualifiers-order":["P17"],"id":"Q281$391b4300-4f5c-ddb6-418c-5fcb5d1da013","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P38","hash":"464d17784bd9ba5f069797ca198f5e5e3352e277","datavalue":{"value":{"text":"2-satisfactibilidad","language":"es"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","qualifiers":{"P17":[{"snaktype":"value","property":"P17","hash":"6916893593b90dd0c3f5ed6f46b3b1bbc7e8a7b0","datavalue":{"value":"Q4596967","type":"string"},"datatype":"external-id"}]},"qualifiers-order":["P17"],"id":"Q281$0aa43ade-48dd-e2fb-b94a-1ca371f57a4a","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P38","hash":"cd48e25f0fc2fda3d2d0e264fe63f8f37fe85b86","datavalue":{"value":{"text":"problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","qualifiers":{"P17":[{"snaktype":"value","property":"P17","hash":"583d76e313f6be92859b0a491a4509746b5df9ca","datavalue":{"value":"Q3435924","type":"string"},"datatype":"external-id"}]},"qualifiers-order":["P17"],"id":"Q281$637f9905-4173-9ee9-07ab-bddaa8aac8e0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P38","hash":"a626f82937907aa5447c09659c91aa811f961b05","datavalue":{"value":{"text":"problema","language":"es"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","qualifiers":{"P17":[{"snaktype":"value","property":"P17","hash":"583d76e313f6be92859b0a491a4509746b5df9ca","datavalue":{"value":"Q3435924","type":"string"},"datatype":"external-id"}]},"qualifiers-order":["P17"],"id":"Q281$8f32d533-4885-e453-ef33-2155d1954b7c","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P38","hash":"a22c599f58d1cd4855aefa1941f67fe7afbbf6f5","datavalue":{"value":{"text":"complejidad","language":"es"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","qualifiers":{"P17":[{"snaktype":"value","property":"P17","hash":"72174a1b62553b1484260ebeb4274034249c7ce5","datavalue":{"value":"Q5157286","type":"string"},"datatype":"external-id"}],"P18":[{"snaktype":"value","property":"P18","hash":"4ca1ace4c0f35111b18c9cb37dabc6752c091edf","datavalue":{"value":"P10374","type":"string"},"datatype":"external-id"}]},"qualifiers-order":["P17","P18"],"id":"Q281$13e3b436-4eb0-f758-5d4b-3b91bc7285f2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P38","hash":"7fd9d642150321ff8fd933a018b740ea687d400d","datavalue":{"value":{"text":"computacional","language":"es"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","qualifiers":{"P17":[{"snaktype":"value","property":"P17","hash":"1d615abddd4982b181b5a699fde465f83f8698c2","datavalue":{"value":"Q12525525","type":"string"},"datatype":"external-id"},{"snaktype":"value","property":"P17","hash":"b811ce4e70f284f741d2942f01afb42af892000f","datavalue":{"value":"Q622821","type":"string"},"datatype":"external-id"}]},"qualifiers-order":["P17"],"id":"Q281$c4854cdc-4e3f-6125-4f60-832b82388827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P38","hash":"c6d5ee3d510cdd61be923ebd0681b908dc78da04","datavalue":{"value":{"text":"2SAT","language":"es"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","qualifiers":{"P17":[{"snaktype":"value","property":"P17","hash":"6916893593b90dd0c3f5ed6f46b3b1bbc7e8a7b0","datavalue":{"value":"Q4596967","type":"string"},"datatype":"external-id"}]},"qualifiers-order":["P17"],"id":"Q281$c669576d-43bd-cb84-3a22-a61681807de8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P38","hash":"b867a2a3343871220a62b75d4d391e0e803caca7","datavalue":{"value":{"text":"clase de complejidad","language":"es"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","qualifiers":{"P17":[{"snaktype":"value","property":"P17","hash":"cce300b1c6d2dfdb186b91e8616ddb14f118fdd4","datavalue":{"value":"Q908207","type":"string"},"datatype":"external-id"}]},"qualifiers-order":["P17"],"id":"Q281$b4e58636-4c37-3308-9ec6-785fe563f7fc","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P38","hash":"df5e4e4c9e5bbf29bdd53a7302c82a1786d2517f","datavalue":{"value":{"text":"clase","language":"es"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","qualifiers":{"P17":[{"snaktype":"value","property":"P17","hash":"7f0b3bd2e40de28f1afa25a6e090d4cd65c37670","datavalue":{"value":"Q217594","type":"string"},"datatype":"external-id"}]},"qualifiers-order":["P17"],"id":"Q281$a8927509-417a-d459-8bda-c73381990734","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P38","hash":"f07e43d467d606a9b07d116a7c3ffaf26a4393be","datavalue":{"value":{"text":"2-SAT","language":"es"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","qualifiers":{"P17":[{"snaktype":"value","property":"P17","hash":"6916893593b90dd0c3f5ed6f46b3b1bbc7e8a7b0","datavalue":{"value":"Q4596967","type":"string"},"datatype":"external-id"}]},"qualifiers-order":["P17"],"id":"Q281$f1a5c10e-4160-3512-e4b2-2d12828c66cb","rank":"normal"}]},"sitelinks":{}}}}