{"entities":{"Q1087539":{"pageid":1098291,"ns":120,"title":"Item:Q1087539","lastrevid":49023274,"modified":"2026-01-06T12:01:29Z","type":"item","id":"Q1087539","labels":{"en":{"language":"en","value":"Uniform normal form for general time-bounded complexity classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3987264"}},"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":"Q1087539$2675B6A9-7BA5-4D3B-BF44-BA2F16A64FCA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b353574abacfd0d3f1d5cab7b463c4d8224e4139","datavalue":{"value":{"text":"Uniform normal form for general time-bounded complexity classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1087539$A4026555-2E60-4219-9761-A5C783A35E13","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"06f89a0f9b76b32cb5e4b0def6ff4d403a43403b","datavalue":{"value":"0611.03019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087539$03B34DD6-5DA8-4602-8D11-F4106E55920A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"385182645ca1914d5dc4969e2d2421608e9dac4f","datavalue":{"value":"10.1016/0022-0000(86)90034-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087539$B979D819-1FF9-4E46-9CA5-E323235AA3F6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3cfe7feb0a9f29a12954c6b9a9eea15a480f4f85","datavalue":{"value":{"entity-type":"item","numeric-id":790802,"id":"Q790802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087539$F82BC5DB-20BB-4C6F-9483-C9B42DCF2CD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e5342853198866e12b3d7b6e7cf2193caff1d15f","datavalue":{"value":{"entity-type":"item","numeric-id":790803,"id":"Q790803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087539$E1F13995-EFD8-4868-BFF5-D4513B03D294","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087539$FEEEB775-619E-4B31-A63F-00CAF1628796","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1087539$56F23E8D-0D9A-409C-96E7-9776F1A554EE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fed6401c5039439489228ea13a6041ae34f355ad","datavalue":{"value":"Ein Ansatz zum genaueren Verst\u00e4ndnis der Hierarchie von Komplexit\u00e4tsklassen besteht darin, eine ''\u00dcbersetzung'' der komplexit\u00e4tstheoretischen Probleme in entsprechende logische Probleme zu finden.    Die Autoren haben in einer fr\u00fcheren Arbeit ein arithmetisches Formelschema zur Charakterisierung von NP angegeben und insbesondere (durch die Angabe von Schranken f\u00fcr die Anzahl der Quantorenwechsel im Pr\u00e4fix) eine ''Normalform'' solcher Ausdr\u00fccke. Die vorliegende Arbeit vereinfacht diese Normalform und diskutiert ein \u00e4hnliches Ergebnis von S. Jukna (1982).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087539$3B7BD3A0-01DE-4420-8DAA-AD1007182B57","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087539$086E2267-153B-46C8-B3A2-0A93CFAA1FAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087539$FA638A54-8CEB-402A-A005-27BCD464823F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f5c8cc8cafcf020e0749585a54c9f058278949bd","datavalue":{"value":"3987264","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087539$548898E5-2B6E-4C63-8865-0C894B1BEC00","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0862baf222b28375411460baab4ed12b7671802e","datavalue":{"value":"complexity hierarchies","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087539$515B7F7C-FB2E-49E3-A550-DBF57861E054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"75595d3cb5fb44aac0e94294450e3374a2c24204","datavalue":{"value":"arithmetic theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087539$76984A95-6AA6-48BE-8CC8-AE2924F5E2B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"834c45d526445b63ede129bf0252d3b47bed13e5","datavalue":{"value":"NP","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087539$B49F40AD-39AB-458A-9FBE-649BCBF19794","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3a201a8779f110985d707176577b688d9a6216e1","datavalue":{"value":{"entity-type":"item","numeric-id":649735,"id":"Q649735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087539$4937F1BC-A057-41AF-B62F-D89B3CF832E4","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":"Q1087539$985D62D5-6981-4E6A-9D0E-F33528731900","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4b4663a5a57814605a5fcd2cc1c92679a13d0291","datavalue":{"value":"https://doi.org/10.1016/0022-0000(86)90034-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1087539$9DC0D22B-0B2A-4D19-AF64-ECE17A63E158","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c7f1f04a67a83dc58ee30bc8d48a8c9409da9fb9","datavalue":{"value":"W1987141990","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087539$6195BE1E-D661-4A52-8D78-5655494D9E56","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5d9257bacf9dc83d7699c2f8365feb77fa5cc2c","datavalue":{"value":{"entity-type":"item","numeric-id":1171050,"id":"Q1171050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087539$E6C9E345-3912-4774-A5A9-B41CF884988B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce1c0bbddddc86b3bb453c99ebb7b85773f6268c","datavalue":{"value":{"entity-type":"item","numeric-id":790804,"id":"Q790804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087539$99728C0C-0378-4194-A622-38FC0BC4305E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"314bf4c64cfb7142c9575d5bd30a4c7c7fbb5371","datavalue":{"value":{"entity-type":"item","numeric-id":3662621,"id":"Q3662621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087539$7305BF62-563E-438E-AC56-4907CF2A6B02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3c6d07dd80de4de8f6f1d51aa5d78e790a6fd51","datavalue":{"value":{"entity-type":"item","numeric-id":5812175,"id":"Q5812175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087539$F19BBBE4-B348-479C-ABDD-3461709BD92E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4751cb99cfb27abec44f2378f8165a3a9a6376a","datavalue":{"value":{"entity-type":"item","numeric-id":1236109,"id":"Q1236109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087539$14CC0D49-B947-4584-99ED-78961D1D84A9","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":"Q1087539$88F73AB8-09E4-4D6E-A91D-225DCBEA5EBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d52c0db9581841ebd44acd9e63e3afcb427ae0c","datavalue":{"value":{"entity-type":"item","numeric-id":794431,"id":"Q794431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087539$C6B2B84F-088C-48A7-9C69-444BF49389D8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0884c424b0161ca398bc80442cc1c90882da616b","datavalue":{"value":{"entity-type":"item","numeric-id":3751567,"id":"Q3751567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18d8fdf6c6b3d103042c4427f023c9edb43821b2","datavalue":{"value":{"amount":"+0.7337231040000916","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":"Q1087539$BAE0FB6B-C4AA-4675-9BF4-3A6EC1C14857","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd529569030221fe02b566353d8784b62fa3687c","datavalue":{"value":{"entity-type":"item","numeric-id":4425337,"id":"Q4425337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a76f0d7347935965b9acd39a758acacdff16e6c4","datavalue":{"value":{"amount":"+0.6953070163726807","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":"Q1087539$AFF03476-6205-4E11-9A0A-5F87489C3F46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc1603ce771ef71e79916eed403efcafd1ba56b1","datavalue":{"value":{"entity-type":"item","numeric-id":790804,"id":"Q790804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9355abad4490a98a9ac8db1868abf5d25ad723c8","datavalue":{"value":{"amount":"+0.6697636842727661","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":"Q1087539$0DE05F35-870B-4DCA-BCE4-58587C8F9122","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3d835e69c406583637d25fd197db97d8da93d77","datavalue":{"value":{"entity-type":"item","numeric-id":5465359,"id":"Q5465359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c997b9c3378e04a0297ed48de0e4275b0798957e","datavalue":{"value":{"amount":"+0.6643673777580261","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":"Q1087539$1EA7689C-B9D7-481A-B624-E970D5DB558B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d62f170ea73483ba5b0b42f50c8c94b6900b2fe1","datavalue":{"value":{"entity-type":"item","numeric-id":1123616,"id":"Q1123616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aecdbf13c51baad85aa1ef24cd1f2a5a2c9c3bf2","datavalue":{"value":{"amount":"+0.6611396074295044","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":"Q1087539$12F64BE0-7AFE-4C7A-BA4B-054F37BA7D9F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1087539","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1087539"}}}}}