{"entities":{"Q3149879":{"pageid":3160595,"ns":120,"title":"Item:Q3149879","lastrevid":47993011,"modified":"2026-01-03T07:22:31Z","type":"item","id":"Q3149879","labels":{"en":{"language":"en","value":"Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1808487"}},"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":"Q3149879$B4CC0B02-A557-4922-8553-964EFD2E611D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"680318ea2a3718cd131ec73a8aede387c2a3a1ba","datavalue":{"value":{"text":"Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3149879$88F030DE-2132-4D32-BF8E-A7036AAF367A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a8254b8b5fa6632c8dde0c7cb134fdb917565c71","datavalue":{"value":"1016.68060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3149879$45CF439E-D293-46F2-88CB-D5AA70E3FA0D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f65298e09b2edcd6f6568b4a474cf5fdac60d923","datavalue":{"value":"10.1137/S0097539700389652","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3149879$3280B21A-F8B9-4EB7-8E64-73DC0CD23354","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0415bd0270f246392c9f05931d81dfadbf989e9e","datavalue":{"value":{"entity-type":"item","numeric-id":598255,"id":"Q598255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3149879$F107E378-542B-4E72-A609-B4929DC846B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7a25d963ba8459ff509d0f0ec3595c17b9f7f836","datavalue":{"value":{"entity-type":"item","numeric-id":354650,"id":"Q354650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3149879$2E2C61D7-D1B0-463F-ADBE-30BAD8BCD21B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3149879$023F2E29-169F-4622-95F8-8E1F78744EC2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e5fbc16e366ffb1f12a89d1e74ac2844b6efae70","datavalue":{"value":{"time":"+2002-09-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3149879$76449234-C183-4CC2-9AC2-693EC63E3676","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3149879$AEEAC08C-B153-4579-80C7-BFFBBA08B124","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3149879$7B30ABF6-88F7-4CB5-A447-4F0CA35C35DB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0fbf842439c0fc3b909925997299138e57cdf25a","datavalue":{"value":"1808487","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3149879$9EA04761-4CB0-4926-BE5E-BEB3FDD35C83","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6b780876d6cd571fe1e41341c135a10b0acf751","datavalue":{"value":"derandomization","type":"string"},"datatype":"string"},"type":"statement","id":"Q3149879$4F1D7D9D-F07F-4C87-BEED-CC96B8514F06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0539db072e4ee5849e5383c82c9881917950f74e","datavalue":{"value":"pseudorandomness","type":"string"},"datatype":"string"},"type":"statement","id":"Q3149879$3BE20738-1F95-4571-9B4E-9A81391870B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf16bbd4a05fdbd1b003839acc80b324384294c1","datavalue":{"value":"graph isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q3149879$C8BB48B0-AF28-4D10-94B3-F6D71A932157","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8428c3fa111c0542ed22960ce5dd7f76f7043e0","datavalue":{"value":"interactive proofs","type":"string"},"datatype":"string"},"type":"statement","id":"Q3149879$3E2FB1AD-8869-49DB-BCBD-7FA162D67563","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67e3fd30cbddfbeec8b4a417b15f99612f5e87e8","datavalue":{"value":"Arthur-Merlin games","type":"string"},"datatype":"string"},"type":"statement","id":"Q3149879$95046176-AC48-44D4-9BD7-66B6C412D1F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06a0a8f0b1cba640c6325c7b2dbcd8ce5aa738e1","datavalue":{"value":"hardness versus randomness","type":"string"},"datatype":"string"},"type":"statement","id":"Q3149879$91AE6696-1BB4-486F-9E10-073C94E81432","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a839b4dea34a5973572c95af1d1df3c4d35ffb12","datavalue":{"value":"universal traversal sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q3149879$664F5572-92E2-4B37-986E-B9DE4ED2E23C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64b4a1c903bdbad63491df93be09359d9b4e135b","datavalue":{"value":"unique satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q3149879$2B4EECF9-1F64-4EC0-9CC4-4F37608C3D31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1bca5b8f8493e57969b551637f12770d6fc436fb","datavalue":{"value":"learning theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q3149879$A78B5876-3600-4003-A821-DC5289D9FE05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a018daf05917761d7f00ad46c490337e7ec23012","datavalue":{"value":"rigid matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q3149879$0E2A0E12-9D26-4F7B-8E69-E4E5CD2B01BC","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":"Q3149879$1E8F09AA-DB0E-42D5-A8BD-87F3704D613B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8258f034eb09faf2edaad8c22bd3ed375e9003c2","datavalue":{"value":"https://doi.org/10.1137/s0097539700389652","type":"string"},"datatype":"url"},"type":"statement","id":"Q3149879$15892B22-3404-49B0-8A1B-D0CD73DE98B3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ccfcbc12ec8506b94baa9272d1d8f2b54fa4f7c6","datavalue":{"value":"W2083237534","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3149879$FC0184A5-685C-4115-AC37-9E1F7E426076","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"174e573de117702a2dce5b525c0777fa29327136","datavalue":{"value":{"entity-type":"item","numeric-id":2819595,"id":"Q2819595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c39653ded1471309da8265d7cd0ec06330ee4f8","datavalue":{"value":{"amount":"+0.9581183791160583","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":"Q3149879$B9480CB1-42F0-459E-BB46-C1FB7A9941B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c920e7b191a07de1ff82fb439b4803631188054","datavalue":{"value":{"entity-type":"item","numeric-id":1601037,"id":"Q1601037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3f29b617d14bf02fb855da3b749eb10ed25d396","datavalue":{"value":{"amount":"+0.8301950097084045","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":"Q3149879$BB6B58AA-0565-449F-90F7-426C65D0429F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e05f5ce8501b89ede81fdea11dcd89752a6f76b6","datavalue":{"value":{"entity-type":"item","numeric-id":4472503,"id":"Q4472503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0801eb98df04edb16f1c2728534625fbfda3d49","datavalue":{"value":{"amount":"+0.8250852227210999","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":"Q3149879$A4C3A2AD-BAFE-478B-A182-35E3C7A03FB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9d7bda51f6e227e7033f5e00f784ec8e74721cf","datavalue":{"value":{"entity-type":"item","numeric-id":1762663,"id":"Q1762663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fc9a7bcdb667c9f91d5dd18949aa9a76c0ec472","datavalue":{"value":{"amount":"+0.8069128394126892","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":"Q3149879$90061781-4F05-44F6-8212-CA5059D4F98A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6468ff3db8507dda8e02811a7f9518046aa3d7c9","datavalue":{"value":{"entity-type":"item","numeric-id":813315,"id":"Q813315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f2746ad31961bf4c346243ef96c868bddb5cab9","datavalue":{"value":{"amount":"+0.7935521006584167","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":"Q3149879$F2186056-6C60-4F20-B338-DF7D86EC6985","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3149879","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3149879"}}}}}