{"entities":{"Q1887166":{"pageid":1897908,"ns":120,"title":"Item:Q1887166","lastrevid":48380719,"modified":"2026-01-04T13:29:31Z","type":"item","id":"Q1887166","labels":{"en":{"language":"en","value":"Bi-immunity separates strong NP-completeness notions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2118428"}},"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":"Q1887166$FDB6B76D-97F6-4A61-ABB3-8BD8684B8531","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"aa323d4424fa887b3b220738eb8257421d957c91","datavalue":{"value":{"text":"Bi-immunity separates strong NP-completeness notions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1887166$65264FBC-F254-4612-A092-C8E21754CFD8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2a82fa5ebe582cddc2afceccd3feb40a86ac4317","datavalue":{"value":"1078.68042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1887166$60ABDECE-3BF1-432A-9DD3-4937DA343E33","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"717bd7e49187dccbd000704e69f42d17b3b2d5b2","datavalue":{"value":{"entity-type":"item","numeric-id":208054,"id":"Q208054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1887166$71F9D19E-6842-4A40-BB65-EFCA287BA672","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"29b02350197f27ae1879c4b07e2f60550fcfbf54","datavalue":{"value":{"entity-type":"item","numeric-id":161380,"id":"Q161380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1887166$61C79FD2-F02B-4273-8587-903B2FCB2BD8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1887166$2B9E08DC-9034-46B5-AC18-8DA1AB14FFFE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f9270318d08aee06ff5ad0dd5710c08e39d64ffc","datavalue":{"value":{"time":"+2004-11-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1887166$3D4CAF49-D064-4714-990A-54ADEEC2A55B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1887166$61FB261E-5EEA-4538-85F5-7FB61241EFD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1887166$FA4F1DB2-DFDC-4CD0-BCA9-37B13444E56B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c9533976195c41a5aebc3ccb5197d241e764aa44","datavalue":{"value":"2118428","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1887166$54921611-D2A9-401E-9B05-1599B08219BE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b06994431796472ed4158ee258c2bd3e3aceb9f6","datavalue":{"value":"Turing completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1887166$F32FAA3B-3740-4767-881A-CC6AF9FAE972","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4cce6e39b97de5f50d21f347fd701dc89ea7108c","datavalue":{"value":"Many-one completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1887166$8212D908-41B3-45DF-94D5-E0B1A946F936","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"289f9cb52c8db0e4bafd755354d567a7ab06f2f4","datavalue":{"value":"Bi-immunity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1887166$E3D30E5C-9D47-4401-AF60-00AD94846A28","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":"Q1887166$53AFFC8D-306E-4D1E-BA4F-24D16DC85991","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"edd65e87cb1ec490cb75625e9b971f3ca75d0c62","datavalue":{"value":"https://doi.org/10.1016/j.ic.2003.05.001","type":"string"},"datatype":"url"},"type":"statement","id":"Q1887166$4846B913-3C2E-4B95-AA1C-71FFBB2758E0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"74e154bad2adf19f98bb2d4c583571ca6150bd84","datavalue":{"value":"W1964450092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1887166$A3FE8FC3-1C3C-48F9-B184-E24D71D34E53","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"618602aa0f10419153676886fd3da06a8ac6a145","datavalue":{"value":{"entity-type":"item","numeric-id":5929911,"id":"Q5929911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1887166$3F505E22-E805-406F-B490-286FA66303D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0a8c80fa018cac3e15747981e6c5267473edde9","datavalue":{"value":{"entity-type":"item","numeric-id":1392022,"id":"Q1392022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1887166$4193AE1A-966C-4296-8DAA-81B2C57E5ACF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cfc53db72d247da5f30e677d4e958d296619aa4","datavalue":{"value":{"entity-type":"item","numeric-id":3996675,"id":"Q3996675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1887166$6FB3A11F-56BA-478B-8EC4-AE3EF05ECDA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b77c359d113f74e32b5b8b8a0ffee20f29b60e6","datavalue":{"value":{"entity-type":"item","numeric-id":3690222,"id":"Q3690222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1887166$813194D5-BE01-4CD2-A569-663425F04F97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63034a0e8ecf7544f06162ea0587268e73a64bf0","datavalue":{"value":{"entity-type":"item","numeric-id":4170251,"id":"Q4170251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1887166$C39A2E5A-8920-4C02-8410-CAA3F4B898C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7d15acf9b2dc594da15dc289088a8a93d59b4f8","datavalue":{"value":{"entity-type":"item","numeric-id":1223166,"id":"Q1223166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1887166$D17BE7DE-7760-42CD-96BA-0185E6B3D29A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"898f7abebb2110166fa4d903fdadc4d54bc027a6","datavalue":{"value":{"entity-type":"item","numeric-id":671427,"id":"Q671427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1887166$10BADCDE-CFC3-40F4-9FD8-3DAB1C30635E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a66a579e1cbbdf800611294dda0dfa180c6508c","datavalue":{"value":{"entity-type":"item","numeric-id":751812,"id":"Q751812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1887166$F54D03A7-B7A4-450C-893E-848281D94CB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47bb5430fb40b4bd2ad7cce5d1c1c335b17aafe2","datavalue":{"value":{"entity-type":"item","numeric-id":2784487,"id":"Q2784487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1887166$9E9BD35B-52A2-4949-9A31-174E1A4C68CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd520b49bc58e84d7c227fcb0bc974b432f91cc2","datavalue":{"value":{"entity-type":"item","numeric-id":1166515,"id":"Q1166515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1887166$A98E258D-4678-4C52-B3E3-6D0C0B0AD112","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7d332ec9daf12fb66275367bd4dc3f18fbf50879","datavalue":{"value":"10.1016/J.IC.2003.05.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1887166$6C3EB964-2D42-4B64-8305-331242F9E700","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d92e8b8ec28bb6879a80878ab5b486dab6dc6e5","datavalue":{"value":{"entity-type":"item","numeric-id":4736858,"id":"Q4736858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20ec97df801c85c0fbd1bc7151883117089cb4d2","datavalue":{"value":{"amount":"+0.9969901442527772","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":"Q1887166$1B642196-9659-447C-BE34-D99A902EBD3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a42f9ca66611c1a0b2f282f97e49b216248d97b1","datavalue":{"value":{"entity-type":"item","numeric-id":2480744,"id":"Q2480744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"febe691664b8ac961dfb530b4b2950ee666cf9ea","datavalue":{"value":{"amount":"+0.8710893988609314","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":"Q1887166$924E03F0-197D-4AF0-BBEE-52D587CD0446","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"170cdb3aba648cfbc9313250beabf51cfbb4ab92","datavalue":{"value":{"entity-type":"item","numeric-id":5929911,"id":"Q5929911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d86391e7ea3c0145f01b88d1582e7bb0700f58f4","datavalue":{"value":{"amount":"+0.8116214275360107","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":"Q1887166$938CDBD0-9848-4DB2-8EA6-16638EDAB8EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73204f7e73e6bdc2c21f0e9ae0046129c1f91aaf","datavalue":{"value":{"entity-type":"item","numeric-id":3434997,"id":"Q3434997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d86391e7ea3c0145f01b88d1582e7bb0700f58f4","datavalue":{"value":{"amount":"+0.8116214275360107","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":"Q1887166$F03836AA-65BD-4F5F-BFC5-15B4E614A91D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07235933f75a48f5c57e3c9bfb4f382011172f6d","datavalue":{"value":{"entity-type":"item","numeric-id":2784487,"id":"Q2784487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc90df229c6257683cd45b1c00d7dbc21de13bd5","datavalue":{"value":{"amount":"+0.8114756345748901","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":"Q1887166$BE20BFCD-F915-4EE8-87BC-C4B1CAE73FFE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1887166","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1887166"}}}}}