{"entities":{"Q582905":{"pageid":584672,"ns":120,"title":"Item:Q582905","lastrevid":57103263,"modified":"2026-03-26T15:47:22Z","type":"item","id":"Q582905","labels":{"en":{"language":"en","value":"Nested satisfiability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4131655"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582905$90E78E7C-7965-4FD8-93ED-5761A9CA294B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"af63893c735941906b2b4c59319901c5d0c05035","datavalue":{"value":{"text":"Nested satisfiability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q582905$63649D82-5CC7-41D1-8A8A-06B21CA0D918","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6b8025375e8fe284cd795f07d8ff43a6c6d79495","datavalue":{"value":"0691.68040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582905$A33184F6-CFD6-4974-B85B-7483C947C570","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e4ad503a1b64b41a1707bea883a14f4077133b77","datavalue":{"value":"10.1007/BF02983372","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582905$97686AE2-439C-42BF-BCCF-8D1DD81BA2EA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"90a6d128b6a220a4d373d17f2e88855fceb57250","datavalue":{"value":{"entity-type":"item","numeric-id":536602,"id":"Q536602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582905$23A5BE9F-7F06-4F7C-817A-61574202E92B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582905$8E20064B-6A65-4D1D-8253-12AB906C51D2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q582905$51EAB031-0556-4481-A22E-0A7D509CA443","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0dc9503fa7f988796305183ee3b1d9a7614e0cd7","datavalue":{"value":"https://arxiv.org/abs/cs/9301111","type":"string"},"datatype":"url"},"type":"statement","id":"Q582905$034CAD03-BBDA-4D21-B104-15B6EDF64F5A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f9e9d67529c413e17c8e0be9e2ed8422b8cdf0a9","datavalue":{"value":"A special case of the satisfiability problem is shown to be solvable in linear time. This special case is essentially ''one-sided planar satisfiability'': It is means that the bipartite graph whose vertices are variables and clauses, and whose edges run from variables to the clauses containing the variables, can be represented in the plane without crossing edges, with all variables appearing in a straight line, and with all clauses on one side of that line. The linear-time algorithm assumes that such a representation has been given, and decides whether or not the clauses are satisfiable by dynamically replacing clauses by simpler clauses containing only two literals. (The running time needed to decide whether or not a given set of clauses has such a nested structure is not considered.)","type":"string"},"datatype":"string"},"type":"statement","id":"Q582905$E9797848-9B45-4BEB-B30B-36A5856957A3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582905$4BE6A7B8-482B-4483-A3A5-E05E97B6AFE8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fd1e1684f82e07b17519449b2a13c1abade7d4a5","datavalue":{"value":"4131655","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582905$7BB95EF6-4795-4AEF-8638-D169D4F12D38","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f0b4d6e6089943a261128dec792d30fd4cdc9763","datavalue":{"value":"satisfiability problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q582905$E46299F1-8746-4239-A94C-D79825FA9AD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q582905$6CEB28F9-12E7-4BB0-8637-C32CD01CCD52","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582905$9FA205FF-1CD5-4C4D-A8E8-CADC276F8258","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"176f92be0a5c8084cbea32a162c15c6e5a582bd9","datavalue":{"value":{"entity-type":"item","numeric-id":3936195,"id":"Q3936195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582905$1E62EA66-6530-442E-8AA0-E706096E704E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ad4a211ceeb1bc0d9d7753eed5bf725110b58bbe","datavalue":{"value":"W2913068454","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582905$D6FA081D-048C-4752-BC78-0134A2502B66","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"438ca1492819dc9e73a8c603ef8ddaa7f71a92bf","datavalue":{"value":{"entity-type":"item","numeric-id":4032119,"id":"Q4032119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63f376dd6ecaebbbee7a43707e019fea4bc52ddc","datavalue":{"value":{"amount":"+0.7947964072227478","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q582905$E9B3F316-AE36-4548-BFC3-97C1C4BA86B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d1fa86bb5f67d0f806395b601846298917bf334","datavalue":{"value":{"entity-type":"item","numeric-id":1082830,"id":"Q1082830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dba81f940091d72d9cc19049db816ee2e93a2c09","datavalue":{"value":{"amount":"+0.7924925684928894","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q582905$5A7678C7-A226-4AFE-A949-80AC2DDC633A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c48f56e941190cd2911d5ff958db66c22ca9b5c","datavalue":{"value":{"entity-type":"item","numeric-id":1114394,"id":"Q1114394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"018e69603f65437f27de9af7c0f7e27d0e336294","datavalue":{"value":{"amount":"+0.7911365032196045","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q582905$47931F67-0D14-4748-AC68-8DD297CFC492","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ec842c2d308234152e050e7702692de7debc5b1","datavalue":{"value":{"entity-type":"item","numeric-id":1323332,"id":"Q1323332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80deb676a9524fcb82be1087d9792d738d60f72a","datavalue":{"value":{"amount":"+0.7885374426841736","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q582905$116F0306-B674-4135-99EC-20D1D8FB165B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24ec9455f54c32283ad7953bf6c8ed6237e5816a","datavalue":{"value":{"entity-type":"item","numeric-id":790612,"id":"Q790612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8465d35e433cbc627af2bc391f60516c35201f5","datavalue":{"value":{"amount":"+0.7864216566085815","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q582905$1B942E4E-8891-4232-8B09-D47750CF5518","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:582905","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:582905"}}}}}