{"entities":{"Q1195855":{"pageid":1206604,"ns":120,"title":"Item:Q1195855","lastrevid":69864120,"modified":"2026-04-13T10:51:13Z","type":"item","id":"Q1195855","labels":{"en":{"language":"en","value":"Deciding whether graph \\(G\\) has page number one is in NC"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 86083"}},"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":"Q1195855$B3893F90-416F-4095-8982-6C6813203478","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"efec6673b7bbe93cfe96cceae0ff78e177fafbac","datavalue":{"value":{"text":"Deciding whether graph \\(G\\) has page number one is in NC","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1195855$6148378F-120D-4F41-B8FD-D2D76B159FE5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cb8437fcdc26ea8699fb5e4ace8cbc45eac9a9d3","datavalue":{"value":"0764.68052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1195855$0C7FE6F4-9908-4EAB-B7DA-140E9C75E09B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bf20e32e7c2004c6f9cd4d99f5a41d11d9e34375","datavalue":{"value":"10.1016/0020-0190(92)90247-S","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1195855$9612D448-DC25-4E10-871D-3B5B57002D4A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"72fc89bef942d51de97d8eea8ee1f5144fd6b625","datavalue":{"value":{"entity-type":"item","numeric-id":287106,"id":"Q287106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195855$208FF3F4-B2A7-41B0-AC93-39ECCE5CF8B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"069f07d5687afcb271d4560351ef0aec2d47d2c1","datavalue":{"value":{"entity-type":"item","numeric-id":1195854,"id":"Q1195854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195855$DD1AE87B-46A3-429D-BEF9-888DC625503E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195855$68C7613C-1530-47E7-B31A-3ACD5E94C89A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f3bee3240083f67ede644d9a0d3cc21f34407cae","datavalue":{"value":{"time":"+1993-01-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1195855$55109510-F5AE-4DCF-9B40-301D4ADEA7D4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1195855$956EB3C2-7DE0-4EC0-B05E-B4477443A00D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1195855$9E61558F-489A-43B7-9EF6-2DBB18FCBDED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1195855$4B6F1BFE-F40C-4365-A5EB-7309ADA3A69A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7d1da0077a8a7b2bc83217dd4bd2236f2650771d","datavalue":{"value":"86083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1195855$D6E7B178-4BCE-4CA3-9104-C14B3242CD18","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"048f9206ca171036767288f94b7e7ef6d48fdb8c","datavalue":{"value":"class NC","type":"string"},"datatype":"string"},"type":"statement","id":"Q1195855$0DE38AFA-24CB-4C7D-9C72-4E43B379B445","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6604b135ad29578febd94d7f624bfe4c31d9c48","datavalue":{"value":"parallel graph algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1195855$6E35C644-C648-4750-B325-3DCBAD3F099A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1db4e3cd8c6237e3b25098b483a3ff821c3b321","datavalue":{"value":"forbidden subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1195855$D3F35EDB-3359-49A6-8402-05C408067794","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6237a6f1238b1dd6927c8b9c5df53466c5aaa53a","datavalue":{"value":"polylog time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1195855$95D26270-414C-44D8-A0E3-9C53BD482D11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db1cb3fb70699de077d0fd85cf8088eccac7998c","datavalue":{"value":"page number one","type":"string"},"datatype":"string"},"type":"statement","id":"Q1195855$AD927D24-3A81-4566-8B97-041F0D66A308","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":"Q1195855$C37B7191-8E17-4B27-9F96-FFA8F89486D4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa710993372ece4c9f42453c93261562aa49ebb1","datavalue":{"value":{"entity-type":"item","numeric-id":4730794,"id":"Q4730794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195855$56575206-E6C4-4A99-835A-B93F0469C69E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2860b21ec28091243d6f8b5601ce1d563a55934","datavalue":{"value":{"entity-type":"item","numeric-id":1136775,"id":"Q1136775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195855$C446B3CA-AEF2-4C4A-BBE6-731301C261B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b602d01a898344ce4e168ea2188a5d94cd04e17","datavalue":{"value":{"entity-type":"item","numeric-id":4727445,"id":"Q4727445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195855$509686CE-EAD4-4B19-9DF0-A5852D9548EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df25916ae88cfd882e8cb6b5b5569c6957043ab0","datavalue":{"value":{"entity-type":"item","numeric-id":2394739,"id":"Q2394739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195855$12D11462-CE5C-4799-8031-42ED1DBA2599","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3c04a6c63bff4f80cdf6d1fa23c76258296aa2d","datavalue":{"value":{"entity-type":"item","numeric-id":3992991,"id":"Q3992991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195855$A6085805-034E-42D6-BBE4-9F691245D615","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195855$57C4FC0D-C0F7-45C9-AB06-77CC043BED29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63f91f47820868b07571001e1845fc94de5d126c","datavalue":{"value":{"entity-type":"item","numeric-id":3348421,"id":"Q3348421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195855$30F9FF9D-71B4-4D82-BD4E-AE2F68D8E29D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e93fcc5f5e8911813f16fcd1e3e08e519d9e013","datavalue":{"value":{"entity-type":"item","numeric-id":4767335,"id":"Q4767335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195855$1BA15DC3-9863-4EEB-83A7-C7B7349759D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08f81f051fd1e93873019ee9a1d154ca78458d88","datavalue":{"value":{"entity-type":"item","numeric-id":1837213,"id":"Q1837213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195855$EA4F97E3-7522-4614-A6CC-2E4603DBB609","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd05e4b67b3a31abf197ae994d88fff07d3dbdbb","datavalue":{"value":{"entity-type":"item","numeric-id":1120582,"id":"Q1120582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195855$0D111BC9-4A5E-47B7-968E-E98E4C65F597","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7e1f4faffc2f9164ecc08f75d4929ecd3162373f","datavalue":{"value":"https://doi.org/10.1016/0020-0190(92)90247-s","type":"string"},"datatype":"url"},"type":"statement","id":"Q1195855$CC773F3D-2786-4BDA-9F90-ED9D7B6D6E08","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f580855956e650fd3091e70206dd5d10d176cb5a","datavalue":{"value":"W2023008617","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1195855$81501BDC-B708-432E-9384-1C2686A14124","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc33347d7a42d22bd5315a90d3fb75adfd828746","datavalue":{"value":{"entity-type":"item","numeric-id":1923610,"id":"Q1923610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77d73ed57fd34916b93cf35cf0f85be71a71ea41","datavalue":{"value":{"amount":"+0.7119348049163818","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":"Q1195855$7A476278-5756-4962-89C0-C5CAE92B5EE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61339dcc09868be5bda31d5c2e361ade6cb72ca1","datavalue":{"value":{"entity-type":"item","numeric-id":4028895,"id":"Q4028895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f1b2ebf5b58a2baa5091d19cda64aa9de1c0bca","datavalue":{"value":{"amount":"+0.7116419672966003","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":"Q1195855$11699862-D256-486B-A82F-F6E3BA568087","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8299e3913550159143681808b205341f796363a7","datavalue":{"value":{"entity-type":"item","numeric-id":6487991,"id":"Q6487991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d3ca494c623ee51e793187e2fc550c0b649af65","datavalue":{"value":{"amount":"+0.7052041888237","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":"Q1195855$F28255A3-0ECE-46F4-A7CD-271CB1AC48E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53feb62fc16c72e5648f9e569c4f52194b19f415","datavalue":{"value":{"entity-type":"item","numeric-id":2682927,"id":"Q2682927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45e4e60333c6202d2504f656bcd33d26cea20fea","datavalue":{"value":{"amount":"+0.7030865550041199","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":"Q1195855$780889D6-5514-4C77-9DEB-D73E75C14993","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e0e0df07ee894369d5be8bc34a01d272226cdce","datavalue":{"value":{"entity-type":"item","numeric-id":3785967,"id":"Q3785967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6fcd6f3016f7c4f4264390c3dc09546836ef158b","datavalue":{"value":{"amount":"+0.7024691700935364","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":"Q1195855$95C98A76-4F67-4B9D-A889-6667A4223B18","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Deciding whether graph \\(G\\) has page number one is in NC","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Deciding_whether_graph_%5C(G%5C)_has_page_number_one_is_in_NC"}}}}}