{"entities":{"Q807992":{"pageid":809840,"ns":120,"title":"Item:Q807992","lastrevid":64489377,"modified":"2026-04-11T20:13:26Z","type":"item","id":"Q807992","labels":{"en":{"language":"en","value":"Space-time isomorphism problem is intractable (NP-hard)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4208993"}},"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":"Q807992$7E61F243-DABA-4314-9D5A-17E841C1D729","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"988891b94c225b3c58303b230c0d048afa1e0732","datavalue":{"value":{"text":"Space-time isomorphism problem is intractable (NP-hard)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q807992$BFA22AE1-AEEC-422B-BE52-8E25CD5D973F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9895c72aed5470fb28b50e1ec5885f8d3404eaa2","datavalue":{"value":"0731.53025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807992$E91090DC-08CC-48DE-ACC3-2524D62727F2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c6b40afa7ca27f195f4d6c5c9dc57b963970d2ea","datavalue":{"value":"10.1007/BF00671011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807992$20DB598B-B091-4F4F-B120-DBCD14DCD7BC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"82a3be88549eb59571e2dd1afecf617032b59ace","datavalue":{"value":{"entity-type":"item","numeric-id":168494,"id":"Q168494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807992$C41A87DA-4C32-49D8-9876-D1AD8CA07442","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q807992$FAB4CD94-067B-4C05-9739-4EA9197E7F23","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"249fa605df5a8a8bbacbf4454dcef4b0fec2018e","datavalue":{"value":"This paper deals with the intractability of the space-time isomorphism problem, i.e. the non-feasibility of the corresponding algorithm in reasonable running time. The local equivalence of space-times in the general non smooth case is viewed here as an isomorphic imbedding of finite space-times (i.e. ``uniform'' spaces with a distance function here assumed to be the proper time between causally ordered events). Considering then the finite causal model as a particular case of the finite oriented graph, the author derives the intractability of the isomorphism problem from that of the ``clique'' problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q807992$15DF34B9-C37F-46D5-A007-0F314823D89B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2225ec2622e37175ce6c167308dc1978446a075d","datavalue":{"value":"53B30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807992$2EA9F387-34F0-4469-BD48-8A86536F4B11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e97cad46ba2c45e05dbaf50f8a57d0621b3b9cbd","datavalue":{"value":"83C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807992$59674158-0335-4679-81F1-6EBB36346A13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807992$2B4D25CB-BAED-426C-BE6E-B5A673A90C23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807992$A898B243-3B51-4932-958B-5D15A8BCD0E6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8923b0418d085cc49d5c0dbb1f8cd9122f18e15e","datavalue":{"value":"4208993","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807992$A453FB1B-159F-4239-A382-DA3DE8430782","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3074f0241136cb5b021ee39930e71697a6899bc0","datavalue":{"value":"space-time isomorphism problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q807992$5478C9D6-DAFD-4E68-B69B-84C659C2C23D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4855d56db5e87523859954f563b909387f110847","datavalue":{"value":"equivalence of space-times","type":"string"},"datatype":"string"},"type":"statement","id":"Q807992$B6FB89AB-5499-457B-9E57-C826CE6B0691","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2410d69f9f7a4844563cb43469bac3b6ba501fda","datavalue":{"value":"causal model","type":"string"},"datatype":"string"},"type":"statement","id":"Q807992$245AFA36-07B4-43B6-8D6F-788912B8F6A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"41e712b3e4e3e6e09e1cf21493dde485ad82b860","datavalue":{"value":"intractability","type":"string"},"datatype":"string"},"type":"statement","id":"Q807992$E19A3127-1EE8-4A65-A98F-85A56588184D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2498ed7cf3607871ad6e64c348055a3c8fc89172","datavalue":{"value":{"entity-type":"item","numeric-id":592003,"id":"Q592003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807992$08209E5B-3FF9-4AA3-8D7D-031E0E129C56","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c10cb2ab297b1755912c42b75101602bbaf2436c","datavalue":{"value":{"entity-type":"item","numeric-id":380821,"id":"Q380821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807992$F1A7C2B1-9139-4DF7-BAAB-F6179106E8E7","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":"Q807992$EC4B919D-A17F-4E08-A19A-0D80EAF06047","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"92ebaab7ec50513179728d5c23bd94aee72c3067","datavalue":{"value":{"entity-type":"item","numeric-id":5538720,"id":"Q5538720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807992$0CB2242D-04F8-4760-9802-13ACBA2E8EE0","rank":"normal"},{"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":"Q807992$FDC299ED-826E-4B97-B649-6534E5E3130F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3da477f96805bbc01e7e08d2ff123e0ae0e16b3","datavalue":{"value":{"entity-type":"item","numeric-id":3198469,"id":"Q3198469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807992$E9FA7D77-BDB4-4D25-85CF-83ED1722F8B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38e1b40b2773a78a3d51029e6ab5bb093cab7031","datavalue":{"value":{"entity-type":"item","numeric-id":3896182,"id":"Q3896182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807992$2A6622BC-8CE0-436E-BE71-7B91233176E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8372c43d200ade73a741cf71d319dcb5f8f8b779","datavalue":{"value":{"entity-type":"item","numeric-id":2750560,"id":"Q2750560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807992$C712ECD2-7B14-4CD6-B920-551BD975E21C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5bd443eb3d68a939713c585bcb63021fafdab4fa","datavalue":{"value":"https://doi.org/10.1007/bf00671011","type":"string"},"datatype":"url"},"type":"statement","id":"Q807992$30B6C238-C608-4922-B595-9F5EEDD11A36","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"173f7cf2bad674a49f9e955c762c8a4b34192827","datavalue":{"value":"W2087695187","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807992$A096A2C0-EE3F-4FD5-8E16-3157A13E2F11","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ceafbd67ffdabda7cde4117bf98502cbf5913e45","datavalue":{"value":{"entity-type":"item","numeric-id":2945856,"id":"Q2945856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53ebe79af52a094387ec6b2e7ed39a703520b3f4","datavalue":{"value":{"amount":"+0.8612571","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":"Q807992$CDB9BCAD-5237-412A-9730-19BE1717E77D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14cf9cdf18ee7679148a14a5e5907e66b0adc8c6","datavalue":{"value":{"entity-type":"item","numeric-id":5884961,"id":"Q5884961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03259a1466e2a974db9a86b823cbd4d0b8fb1e7f","datavalue":{"value":{"amount":"+0.8191201","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":"Q807992$36D52C32-5153-4492-82B4-85DD1A051313","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5453ee831f64cacc2a1fb52efed6c1e7b3102b8d","datavalue":{"value":{"entity-type":"item","numeric-id":843612,"id":"Q843612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1db300f3e157e07bd0954a8184f31118aca5872c","datavalue":{"value":{"amount":"+0.80689055","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":"Q807992$F86B59A3-54F5-47EE-B04B-E56F39B5D238","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1199dc641914b3f5fc2373b5c1d980c806ca194","datavalue":{"value":{"entity-type":"item","numeric-id":4873209,"id":"Q4873209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a826111e274e678a45d03cc6a7eb261c83ec1eb6","datavalue":{"value":{"amount":"+0.8004848","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":"Q807992$C84748E2-2AE5-4837-B787-DD82EDE516C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c70b8b31dcead08c7065d77698a57d12b23cdc05","datavalue":{"value":{"entity-type":"item","numeric-id":5391059,"id":"Q5391059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22124530468c1012721bc2da0d23778020ef39ee","datavalue":{"value":{"amount":"+0.795583","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":"Q807992$9530059F-D8E6-43EF-A4D3-21DF05BFD8DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"197c18dbb41c267d50e8c6f162323d4c907a1cdc","datavalue":{"value":{"entity-type":"item","numeric-id":2906562,"id":"Q2906562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1750979df53c3807d3daa2d553671d427c687e9","datavalue":{"value":{"amount":"+0.7922315","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":"Q807992$796D3CEB-44F2-41B4-A1C7-C774D673DA65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c26b8482422a145f8f82f63b07a9c38bb14134ad","datavalue":{"value":{"entity-type":"item","numeric-id":949614,"id":"Q949614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7444428dd4e3b4570b78f1c956b4b6b3da645b1a","datavalue":{"value":{"amount":"+0.7913945","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":"Q807992$A18257D8-2C5B-41B0-A8D5-3E27F2C43DEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25c19caec50c0764effebe546295dcac93045a41","datavalue":{"value":{"entity-type":"item","numeric-id":3747622,"id":"Q3747622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbaa5ebe0eea2a5141ecc52a66b2c921b3c27d04","datavalue":{"value":{"amount":"+0.7904471","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":"Q807992$DE8847D0-2B2F-4641-A98D-70F2CD1E45AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a597342997d402b0b63e104b43d2916c35f0ceb9","datavalue":{"value":{"entity-type":"item","numeric-id":3200187,"id":"Q3200187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8183ffc46971cd44992946c2db91ea876e093f1b","datavalue":{"value":{"amount":"+0.79008055","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":"Q807992$994A075F-C26A-4CAB-9A67-86F0EDC14906","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c00c1b3ddff869e66db31c89bc28dfe37ab26924","datavalue":{"value":{"entity-type":"item","numeric-id":3483446,"id":"Q3483446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17091fec81427f56c90a425217b16efc08f06dea","datavalue":{"value":{"amount":"+0.78314006","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":"Q807992$91DC996F-AA9D-40B6-8413-D2A573F135F6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Space-time isomorphism problem is intractable (NP-hard)","badges":[]}}}}}