{"entities":{"Q1064779":{"pageid":1075531,"ns":120,"title":"Item:Q1064779","lastrevid":66066420,"modified":"2026-04-12T07:18:43Z","type":"item","id":"Q1064779","labels":{"en":{"language":"en","value":"Complete problems for space bounded subclasses of NP"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3921976"}},"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":"Q1064779$D14E4296-DC1F-4EA6-B570-BBA35AD474E8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"60b4ef3038629b1fc8d3c849dd6ba5176e9c74c2","datavalue":{"value":{"text":"Complete problems for space bounded subclasses of NP","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1064779$C1389732-DD30-4444-B611-67801C092E0E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"43d892bf860c8324091e92ce49f48db7dba965f8","datavalue":{"value":"0576.68031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064779$A583C7A1-51C3-40F1-BDC8-C34575589047","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fdb5024526ee09c6012c23ca1ec01117df870a83","datavalue":{"value":"10.1007/BF00288774","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064779$DC2EE7E6-C534-4F7F-B0CB-AFF23AFE4D21","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"41478f89a07e1ef5c2b2b6407437f9167f25e806","datavalue":{"value":{"entity-type":"item","numeric-id":1064778,"id":"Q1064778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064779$C02B56AA-B3DC-4159-B619-2F2AC5D417A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"619555d96850b0d2a63f38f6976c99450dd5b2d1","datavalue":{"value":{"entity-type":"item","numeric-id":791315,"id":"Q791315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064779$9545D6DA-258F-4BFC-B2AC-8FE219F9963A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7825b3d102ec704698f1b08fb699671765eaeff2","datavalue":{"value":{"entity-type":"item","numeric-id":910214,"id":"Q910214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064779$9FE80E1C-0D14-461B-81B5-45AA2FFF50AF","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":"Q1064779$7252BC8B-940E-497C-99FC-A188BBEA976B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1064779$F868C4DF-1CF4-4780-8A1C-38D7B8B2A06A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0a52f20f08509c7a8070570d88f7d140b102c8bf","datavalue":{"value":"Some problems are proved to be complete for the classes NTISP(poly,f(n)), for a function log \\(n\\leq f(n)\\leq n\\). For this purpose the notion of bandwidth of a combinatorial problem, introduced by Monien and Sudborough, is involved. For example, in case of the problem 3SAT of satisfiability of 3-CNF, denote by 3SAT(f) this problem restricted to 3- CNF, \\(w=\\&_{1\\leq i\\leq n}(y_{i,1}\\vee y_{i,2}\\vee y_{i,3})\\) such that for any variable x occurring in i-th and j-th clauses (positively or negatively), the inequality \\(| i-j| \\leq f(n)\\) is fulfilled. The following problems are log-space complete for NTISP(poly,f): NOT-ALL- EQUAL 3-SAT(f), DOMATIC \\(NUMBER_{k=3}(f)\\), MONOCHROMATIC TRIANGLE(f), CUBIC SUBGRAPH(f), DOMINATING SET(f), ONE-IN-THREE 3-SAT(f), MONOTONE 3- SAT.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1064779$CA08F748-F1EB-4C59-A1F3-60AD3C562557","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064779$D76C8DC0-399B-4DAE-B46A-14C7AF676975","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"efb5e23d5e95d883be46ef82c89f286f78449741","datavalue":{"value":"3921976","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064779$18EC722F-B855-4FCE-A88C-3ABE98C2D1F6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fde0e138710a83fd4e15b2eee94c85e9a821481e","datavalue":{"value":"space bounded class","type":"string"},"datatype":"string"},"type":"statement","id":"Q1064779$2CABAD68-12CD-4C81-AAEC-9AD0971193D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e4ef85572bb0c4b58c91b4f071f3b801bb5e6d32","datavalue":{"value":"bandwidth bounded problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1064779$7BAE54D0-0479-439D-BE8E-B65084C6A2AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"18c219a0f38adc0fb2af4f140d791ac0ef8b22c7","datavalue":{"value":"log-space complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1064779$44C404B9-58D1-4992-8A48-B71A4217F090","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":"Q1064779$287DE595-1D7A-43D5-91D5-D5293947DA50","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064779$EFB5E231-C6D2-47B8-8F54-5CAA4BD4220B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93abefd43f60c4734d29bc653212ccc79b537d1c","datavalue":{"value":{"entity-type":"item","numeric-id":4165413,"id":"Q4165413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064779$CCFA2C53-DACA-40F0-989F-D8582519FC8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064779$A610030D-78CE-4A23-87F7-9F339D73AAA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2b7958dc2b7884b86126cf911b9071d9ab73aa9","datavalue":{"value":{"entity-type":"item","numeric-id":4115165,"id":"Q4115165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064779$EE2EF619-458E-4889-8B08-5E8BAFBEF3C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abd01152085dc6c923faefae39879822e508a915","datavalue":{"value":{"entity-type":"item","numeric-id":3219762,"id":"Q3219762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064779$FD9C230C-49F8-45DC-8511-27CD162CE85F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064779$E4E16774-331C-485E-A65B-7AB5FF81F418","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bcd71ac0ee1662e3c5c0f5046af9d7c75419ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1221749,"id":"Q1221749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064779$E55C4B4F-0D70-4074-9BF4-DDAA3E276424","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e1f0209c662a26c652a065cc280f3e4e1081f4d","datavalue":{"value":{"entity-type":"item","numeric-id":1822500,"id":"Q1822500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064779$F7D1EFF6-D3E7-4AF5-9C22-3B40478A09F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcaa8b55397625a2950f7d798fc80eeb38eeafc9","datavalue":{"value":{"entity-type":"item","numeric-id":1168735,"id":"Q1168735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064779$0477E854-5A78-49A7-AE04-BD15F964C102","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24f4aba8e0ee3a2966b3de817d74f8875ab291ae","datavalue":{"value":{"entity-type":"item","numeric-id":1223124,"id":"Q1223124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064779$D96F091F-D5DA-42CE-B6AB-FB69C6693649","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c30b66ff2b3993baa31f89ad45be8a5ecb924076","datavalue":{"value":{"entity-type":"item","numeric-id":1838912,"id":"Q1838912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064779$416E3D79-41C0-4165-95F5-71A15CB670A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736a1d463d18d2f300e2b9600c3f86eae2986ef8","datavalue":{"value":{"entity-type":"item","numeric-id":2537313,"id":"Q2537313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064779$F75D8FCA-836F-4F59-BE46-F68253BEEA80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e759b8ddc389f8b42bb244f19be1adfe6bb34c7","datavalue":{"value":{"entity-type":"item","numeric-id":5402560,"id":"Q5402560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064779$0BD5A98A-0471-440D-AFA1-EC1E0E03DB24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"977c0a28e22a20f1da6609124ac2c8bd23eb43d0","datavalue":{"value":{"entity-type":"item","numeric-id":791316,"id":"Q791316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064779$B7CD17C7-1DED-4BAB-A0EB-D83AFAF9E85F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"694b2e084e8bf3578a9b75d45960bffba3ec7a2c","datavalue":{"value":{"entity-type":"item","numeric-id":1169277,"id":"Q1169277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1064779$C99108B8-F42A-4D64-82FA-8507D5F7C2D3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dbe820734cd9a4e5c0d4273106f8e074fc1b8b05","datavalue":{"value":"https://doi.org/10.1007/bf00288774","type":"string"},"datatype":"url"},"type":"statement","id":"Q1064779$07F96F31-9166-408F-8BCE-DC1D8097D10F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b27a8e08bf7ec1f5251ce08ae09805ff7bd88e80","datavalue":{"value":"W2056508159","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1064779$AAC348EE-8CD4-433C-83FD-1818B53FCC20","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa82dc0720d1d3ce37ab93ca5e1cbba583cb4cc0","datavalue":{"value":{"entity-type":"item","numeric-id":1822500,"id":"Q1822500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0080c51f2c65028311ec9f64a2aaee12e17fdf09","datavalue":{"value":{"amount":"+0.8795409202575684","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":"Q1064779$06A5894D-6E87-4D1F-8215-6A8E22CD0EB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1114e1692121c0b1f5cab4f3307d78bb3deafaa","datavalue":{"value":{"entity-type":"item","numeric-id":791316,"id":"Q791316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cbf3f39d2c63559850c290d61a959537d9982590","datavalue":{"value":{"amount":"+0.7940518856048584","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":"Q1064779$807CA2C9-217F-4DC9-A1F9-E42D0013ACAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e04546efc41dad6d5fc4dddd71909771876c6131","datavalue":{"value":{"entity-type":"item","numeric-id":1262855,"id":"Q1262855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b7af13f6608afe6b317f4635e5d45684b3ce16a","datavalue":{"value":{"amount":"+0.7818179726600647","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":"Q1064779$56A3C4DF-77F6-48E7-AD82-42B47B00F650","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5bf38cc888921590df143be54d6b97aac5f0ba8c","datavalue":{"value":{"entity-type":"item","numeric-id":4668733,"id":"Q4668733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54a6b8b4ca31c04b0a00f8b3c9cae9cc5a936402","datavalue":{"value":{"amount":"+0.7681369185447693","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":"Q1064779$D63293DF-BC39-4208-9DC3-ED660C4515CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13d70deeb26906d5c64fe5cb5aef806091cc3c03","datavalue":{"value":{"entity-type":"item","numeric-id":1338895,"id":"Q1338895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1e067c927b6b99aa76f93917943a98d95aff6bc","datavalue":{"value":{"amount":"+0.76543128490448","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":"Q1064779$DB87BEC5-F20D-4A51-8AEE-686778B0DE09","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complete problems for space bounded subclasses of NP","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Complete_problems_for_space_bounded_subclasses_of_NP"}}}}}