{"entities":{"Q1777396":{"pageid":1788138,"ns":120,"title":"Item:Q1777396","lastrevid":43324350,"modified":"2025-07-24T17:56:48Z","type":"item","id":"Q1777396","labels":{"en":{"language":"en","value":"The complexity of homomorphisms and renamings for minimal unsatisfiable formulas"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2168186"}},"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":"Q1777396$87984B36-02EC-4492-9073-73E369FF0354","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"46a98968f5da0e67487a8ea8e593bbf3121991a1","datavalue":{"value":{"text":"The complexity of homomorphisms and renamings for minimal unsatisfiable formulas","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1777396$656DE2DD-F634-46EA-A84E-A9E9B5BC8D5E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c6da753131ce6f32cc34a0978fe3da6878eaeb6c","datavalue":{"value":"1099.68040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1777396$D1B48E56-B778-4D91-89DA-BAF6BC1E95FD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9fa6eeb09e47d0c3657c971f131f2ff7452bd83e","datavalue":{"value":{"entity-type":"item","numeric-id":599500,"id":"Q599500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777396$7F0FFB1C-8939-429D-B732-50045BE2E723","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1d1cfac4fcc4acbf6b4ed2adbfa6f6821da971d1","datavalue":{"value":{"entity-type":"item","numeric-id":1040958,"id":"Q1040958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777396$91FC1125-C79E-46D5-9C6C-E1CD5AC022AB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7346dc34d1d50fea46ec345fbc7e3214530889ab","datavalue":{"value":{"entity-type":"item","numeric-id":276517,"id":"Q276517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777396$F09C509F-C41B-4187-AFDE-1A1D2E960666","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c64595f4f39ba5aa8c317730455f9500451c9c2e","datavalue":{"value":{"time":"+2005-05-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1777396$580D75FA-69AB-4B6B-89EB-4DC1313433F1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1777396$58908B52-2D5B-47BF-BD33-71D27CCC2CDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1777396$82E2F1E6-7775-403C-B64C-1C595724F180","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"67d040c1068d7628386c3125a387c0cb5ee811db","datavalue":{"value":"2168186","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1777396$3D484979-3166-4DF3-B9C5-07F9D7D470EA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1777396$2D9AE8AE-F2D6-4FC8-95E3-7ACC4768286F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88ac52ba5fbfea503a5169a1bf75445d6498e920","datavalue":{"value":"renaming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1777396$3514447B-34BF-4DF8-81F7-9B1708F44541","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e636d6200f7544f4dd5a5bbed79f99982c70f6d","datavalue":{"value":"homomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1777396$D50AF89D-A60B-4575-9B01-18253D00D6C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5091200f3a7a2dda9a1bb616cc9920b4d5034101","datavalue":{"value":"minimal unsatisfiable formula","type":"string"},"datatype":"string"},"type":"statement","id":"Q1777396$DCB73146-032B-429B-BBCD-2C000467B38F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf16bbd4a05fdbd1b003839acc80b324384294c1","datavalue":{"value":"graph isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1777396$53CEACF3-F6CD-4245-947C-28E37A366730","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":"Q1777396$4340DA69-8A89-40F2-9A54-566DECECFFC6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a6bd573010dfb32fd7c89350a1065942bad80a87","datavalue":{"value":"https://doi.org/10.1007/s10472-005-0422-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1777396$5208B9FC-33EC-4FEC-B9E9-96F2F8E45456","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"65d1b8f3a43237316ac5b1847da2e276591c6dc6","datavalue":{"value":"W4256737158","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1777396$8815DCA4-D1F0-4048-9D26-952BA075FF73","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"725c84c2ebc6f4b154eb6d601e5b793715036a34","datavalue":{"value":{"entity-type":"item","numeric-id":1087560,"id":"Q1087560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777396$7969839A-1230-46AF-BFE7-B9939E01DA59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c56aaf8ccd46e3192e050c0368f83b3d69dc51b","datavalue":{"value":{"entity-type":"item","numeric-id":1277336,"id":"Q1277336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777396$8C99FC9E-280B-4A9A-98E8-BA15CC0318BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3af833cb6c2f278650e57fa9adf052fcaf7a52e2","datavalue":{"value":{"entity-type":"item","numeric-id":1853541,"id":"Q1853541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777396$56B09550-5973-4CDC-BC66-7EABFA8EA52F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fec165abc7ade014841f417bcba31a647c17e0c7","datavalue":{"value":{"entity-type":"item","numeric-id":1100215,"id":"Q1100215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777396$447AE806-972E-4830-9137-6BAC1B0D0D57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49028d8775bdf9fd494597e7926eb3a6bde9a5a5","datavalue":{"value":{"entity-type":"item","numeric-id":1853126,"id":"Q1853126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777396$6E5BA851-F76C-4C9F-80BA-B97D0C75E256","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aff365d8186cc4c7ca2a8c01bb1842652c3c232d","datavalue":{"value":{"entity-type":"item","numeric-id":4273947,"id":"Q4273947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777396$9521996E-EF58-4CB8-A4C1-BB51CE97BA20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9039c5b03ce44bd1ae984dac18752d8859c6d482","datavalue":{"value":{"entity-type":"item","numeric-id":800909,"id":"Q800909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777396$9C46DE35-41A6-48ED-94C0-B4CBF0A4B83A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ebf50b3b231b28dd36b98369bafa45d547ad97d","datavalue":{"value":{"entity-type":"item","numeric-id":1109565,"id":"Q1109565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777396$98DA716A-049A-4C7F-BE9E-8D6A5BB8F833","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"def643ba426dace1e4379bfd001d506cb1e71a1d","datavalue":{"value":{"entity-type":"item","numeric-id":1408387,"id":"Q1408387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777396$8B6A73A4-3E0F-4B8E-9557-9C43E639EEA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5d2a85fd0daac5ebbfe9d1d095a6735cbaa6d82","datavalue":{"value":{"entity-type":"item","numeric-id":1961453,"id":"Q1961453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777396$E71F97F5-2AE7-4F8F-B706-17E90AC1CBC6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6ba58711037bd5817eaa3c291103aeb9b349ae97","datavalue":{"value":"10.1007/S10472-005-0422-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1777396$C5D00DB6-A710-4FBD-9A56-E2932BE05AA3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"103d5b4da1f69720b579cf5f7a30ea292acbb947","datavalue":{"value":{"entity-type":"item","numeric-id":3434502,"id":"Q3434502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"295f0aadb8768cbad96c91f86704dc59c50ad29c","datavalue":{"value":{"amount":"+0.9093044","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1777396$F42FA6BB-3D6E-4303-92D1-B533DD9EF07B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45f3b959abc5df196425724c440feff6626db7e9","datavalue":{"value":{"entity-type":"item","numeric-id":5309031,"id":"Q5309031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a4a32a8b3783135a2ccc19037b2d5930aac6d4f","datavalue":{"value":{"amount":"+0.9034694","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1777396$7D54CD43-6E62-46B1-B0F3-7BE514054391","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6a5c8ae31c3607e38ec583bb9716d93898aa4d7","datavalue":{"value":{"entity-type":"item","numeric-id":1010894,"id":"Q1010894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5307f805ffcbf06af19618011a00a5f577153a9","datavalue":{"value":{"amount":"+0.8921596","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1777396$608639C7-71C4-42CF-8143-F8CD79B6BC03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b496d73cc71f03723d822ff7533eb9713f4da25","datavalue":{"value":{"entity-type":"item","numeric-id":5473177,"id":"Q5473177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abd9e1cb91ad56e0e469c9bfcc9b3484d4bf9b47","datavalue":{"value":{"amount":"+0.88335454","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1777396$0631C3DA-D6C4-4FCD-BD1A-716EEC5076DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8c216e01641a6f7ea45e58d744d7ba1fd6bda1e","datavalue":{"value":{"entity-type":"item","numeric-id":1887137,"id":"Q1887137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0137b1ee7e4498d82e19b729fe4a0cf909b31e3e","datavalue":{"value":{"amount":"+0.88209903","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1777396$4F142419-B990-447D-BDC3-0DF6380D4349","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3fda2a6f8fe8b744fa34dcb1c77a9ba67ecd8067","datavalue":{"value":{"entity-type":"item","numeric-id":2762521,"id":"Q2762521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0137b1ee7e4498d82e19b729fe4a0cf909b31e3e","datavalue":{"value":{"amount":"+0.88209903","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1777396$A56880B1-EDEA-4D72-BF83-E7C94D7EC5EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af997b1ce1d14533e9566f689db18ee8b858d118","datavalue":{"value":{"entity-type":"item","numeric-id":3546332,"id":"Q3546332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"688f484646593672eb8c83943386e7fff730514d","datavalue":{"value":{"amount":"+0.87593234","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1777396$6DB6BBA5-10E5-4BA7-B4DD-3CF4D16CE366","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8ecb93b794022b0047bafb37df1c9cc3623ea6d","datavalue":{"value":{"entity-type":"item","numeric-id":1853126,"id":"Q1853126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"225bb9d409644eb30ee084fac67a862686a93fc7","datavalue":{"value":{"amount":"+0.87530816","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1777396$DA7162D5-7B26-4160-B081-B3E096E3B8C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"875e8f2bfecf0bcbd77fc501b60ebbd080fc3230","datavalue":{"value":{"entity-type":"item","numeric-id":2743691,"id":"Q2743691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"293be1219be85cb44c59ca0f3262bd73fcd75315","datavalue":{"value":{"amount":"+0.87469774","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1777396$B37202BC-A9A3-44E9-9E08-65981683E79D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2cfb41756e8ccfefb4b225fce6e9d3280f5e028","datavalue":{"value":{"entity-type":"item","numeric-id":1841884,"id":"Q1841884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4901d33a812d4261f062afea4f4622fe1d65fe37","datavalue":{"value":{"amount":"+0.87452406","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1777396$B5A0ADF0-7181-4023-8AB7-7A220DCB6F22","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1777396","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1777396"}}}}}