{"entities":{"Q795829":{"pageid":797677,"ns":120,"title":"Item:Q795829","lastrevid":64398966,"modified":"2026-04-11T19:36:29Z","type":"item","id":"Q795829","labels":{"en":{"language":"en","value":"Oracle-dependent properties of the lattice of NP sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3863183"}},"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":"Q795829$68FA99D3-AA00-4456-B7BD-F4DA784F9C21","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b46bc749e7757555a35af1c28c6ee8908f483b3f","datavalue":{"value":{"text":"Oracle-dependent properties of the lattice of NP sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q795829$2AD7F2A9-223A-4FB8-BCAA-D08468B71156","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b61d2299b4cb2f9cb85d3e8395441eca09f36b44","datavalue":{"value":"0543.03024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795829$2056BDFF-CF86-4816-A809-7DC60F63AA8E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e0dcafe2bf6cffacba9f9afe9dbb9662d2a55f90","datavalue":{"value":"10.1016/0304-3975(83)90003-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795829$62CE7B5E-C0C6-47EF-8C0A-9F5442AF6B25","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d78494649a50abfeb7718b8ac650c7c073c553a9","datavalue":{"value":{"entity-type":"item","numeric-id":353853,"id":"Q353853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795829$4B1580A9-3A16-4FB0-B785-3B8B0B6B460B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"24978249bb6f26d3c70c78605ce95b13704fc350","datavalue":{"value":{"entity-type":"item","numeric-id":161379,"id":"Q161379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795829$FFD9345E-27EE-405C-BD1C-3557045664D5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795829$B0347820-943B-47BA-9316-E8A5DD6B51CB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q795829$7F47577B-2680-4CF2-91CE-DA4AB06F439C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5ca8aa8692a0fbec803204fc8f864a3b0c87dbea","datavalue":{"value":"The paper considers questions about the lattice of NP sets, together with the sublattice P, under the assumption \\(P\\neq NP\\). Two properties of NP sets are considered; whether there are any simple sets in NP and whether every infinite NP set contains an infinite subset in P. An NP-simple set is a coinfinite set in NP whose complement contains no infinite NP set. Oracles are constructed relative to which \\(P\\neq NP\\) and for which the statement that NP-simple sets exist is true, respectively false. Similarly, it is shown that any argument which solves the problem of whether every infinite NP set contains an infinite P subset does not relativize. In particular an oracle B is constructed relative to which \\(P^ B\\neq NP^ B\\) and every infinite set in \\(NP^ B\\) contains an infinite \\(P^ B\\) subset. The considerations are analogous to the study of the lattices of recursively enumerable and recursive sets. The constructions are somewhat more sophisticated than those previously used in this context.","type":"string"},"datatype":"string"},"type":"statement","id":"Q795829$83C2EEE2-EABE-4CC9-9023-8529DE8CBA0F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795829$10B43F74-23BE-43A7-9422-BAA269AE94CD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"433c0faee4f238dc6a1084878f5795efdb9fec41","datavalue":{"value":"3863183","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795829$2B8895AE-6820-466F-972B-6BBEFC0DCB78","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1a02b4e020864e91f8b46070c7c982fa2878da3","datavalue":{"value":"theory of computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q795829$A3B9BF5F-4CC3-4B11-A552-B7F22230BAB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf3973bce3a7ddc1f11c81dcfcd12b0aafb2fdc2","datavalue":{"value":"intractable problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q795829$A19F8108-2CAF-4065-BF43-440DCC1C649B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0068b0714c901732dad97256b1bb77963d876250","datavalue":{"value":"lattice of NP sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q795829$0CDDBCBC-ABDE-46DD-B102-1E2DC545A01C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab6e04df938671db6a0f08c281be4e60f36d3072","datavalue":{"value":"simple sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q795829$D627DE03-7238-4146-AC96-5D9B394F3BED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe79a42ec8550681ca1ce89abf774fb2d24bf8e1","datavalue":{"value":"Oracles","type":"string"},"datatype":"string"},"type":"statement","id":"Q795829$663C2E83-FD28-4CC3-89AD-79D8BFEC6FDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ce68829d9e8d6f5c54a8839474c5af28bc09210","datavalue":{"value":"infinite NP set","type":"string"},"datatype":"string"},"type":"statement","id":"Q795829$73443AE2-A930-4B88-8CD7-707D97AB742C","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":"Q795829$67AA0DB1-0D2D-472B-905D-42B5925FB52A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"26906fc1087c738efd44d9c778f0ef69a68c0911","datavalue":{"value":"https://doi.org/10.1016/0304-3975(83)90003-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q795829$7FB1DA6F-8619-4806-B6EF-CBD837177519","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"57e5f7da8e06ce39d9070aa5d9d80923bd5f9ea8","datavalue":{"value":"W2059997023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795829$56C73DCA-0168-4324-9287-C678B2B04B08","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c4b58f9e8478a4210509de111b81e4ccd911506","datavalue":{"value":{"entity-type":"item","numeric-id":4086709,"id":"Q4086709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795829$B6AC244D-D159-47A6-9302-F92B4E52260B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54e3771f8171656e0aed45bf0777afe8aad7a3a9","datavalue":{"value":{"entity-type":"item","numeric-id":3902480,"id":"Q3902480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795829$940C890C-AF3B-4395-83ED-EF2EC3B778E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a308524b150ea0978a37c4e6913368e76b231f7","datavalue":{"value":{"entity-type":"item","numeric-id":1251652,"id":"Q1251652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795829$50166A40-71E6-472F-AE5B-CC6ED5D4E31E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795829$D56730E8-2BA0-4E38-9E82-7D455B80CB89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2654c1ad3008ab65ddf962a999d4d8045dcdea","datavalue":{"value":{"entity-type":"item","numeric-id":4085242,"id":"Q4085242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795829$F6DBB964-6822-44DA-97F0-19321AF514AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba17c610b66d156b76e62a37325c965ffedff718","datavalue":{"value":{"entity-type":"item","numeric-id":4184825,"id":"Q4184825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795829$88F84E87-95A3-4DB9-A01E-51938BECCC86","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d9031b73ffb0f4c256e887d2438ff51cf9e7d9d","datavalue":{"value":{"entity-type":"item","numeric-id":3761699,"id":"Q3761699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56320d4877b5ad4a94fb558ec7893640eeaa7723","datavalue":{"value":{"amount":"+0.835332989692688","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":"Q795829$2CCA6C84-82BD-48B2-83F4-53B49B56E418","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25cfb0ccd65f37cea695c84cbcd62c6a48959919","datavalue":{"value":{"entity-type":"item","numeric-id":4278847,"id":"Q4278847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36770fd0b7ddc6d6d6a032264ba784a3cba9baf9","datavalue":{"value":{"amount":"+0.8281799554824829","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":"Q795829$F76C43FE-C973-45CC-80EE-810EFB794224","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"909e21571ee0aa44b4ee0c474aece50eed2f2784","datavalue":{"value":{"entity-type":"item","numeric-id":3691647,"id":"Q3691647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36fabb9839d4eab9c35c23a0682f0cc5bdf70022","datavalue":{"value":{"amount":"+0.8007887005805969","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":"Q795829$7A2036D6-10EF-4F01-BAF5-CF549B2EF879","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"443da56195c385d4cc0144a094c496f296f3735d","datavalue":{"value":{"entity-type":"item","numeric-id":1822968,"id":"Q1822968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0248c70eb3e07118bfa5fbd2462e5d4281420fd3","datavalue":{"value":{"amount":"+0.7985921502113342","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":"Q795829$67A11D6A-874B-4EFE-A494-8E134F9A36BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2ec77b04dcce35ba585aea66a698d36ea6e189f","datavalue":{"value":{"entity-type":"item","numeric-id":582906,"id":"Q582906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ef7e04c7772d248bd76fdc3beb86d366492947e","datavalue":{"value":{"amount":"+0.7958759069442749","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":"Q795829$D4BA5426-8CBB-4891-B4E1-3E092678F4FB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Oracle-dependent properties of the lattice of NP sets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Oracle-dependent_properties_of_the_lattice_of_NP_sets"}}}}}