{"entities":{"Q688157":{"pageid":690006,"ns":120,"title":"Item:Q688157","lastrevid":63490080,"modified":"2026-04-11T13:30:43Z","type":"item","id":"Q688157","labels":{"en":{"language":"en","value":"If not empty, NP-P is topologically large"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 440333"}},"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":"Q688157$7E4A3D4F-348D-41D1-96F8-96E0F4D329F8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cb8e2b02d97f327054266a492ac33446b66b93c1","datavalue":{"value":{"text":"If not empty, NP-P is topologically large","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q688157$2B27F864-B831-41EA-AD19-811397130D26","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7825a9f6cb69821b82af8cfff33d9af2dd51af18","datavalue":{"value":"0781.68072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688157$4E3647B2-9643-4B63-BC51-53DC3BBD5B6F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c87b7c0d9f5500b35dcedab98b159a665abf26f6","datavalue":{"value":"10.1016/0304-3975(93)90161-L","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688157$0CFDB2A2-5AF2-43BF-BE08-6B68D94C9A7E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d750fc05251a9f31c6a44ffc6c9d2225a4eea35b","datavalue":{"value":{"entity-type":"item","numeric-id":290243,"id":"Q290243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688157$845DB5E8-4F87-4125-BDF1-0B599985D7A5","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":"Q688157$E81335A5-0FEF-4EE2-A197-D7F12F593511","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8ece7c460c78874e314a441f2bb630645a5e7532","datavalue":{"value":{"time":"+1994-02-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q688157$1BC4A0CB-8EC3-47C1-BE24-D28316F442BE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"584f58c251ea5ae639cb38e2c5ca94a2b3e875e3","datavalue":{"value":"One shows that in a combination of Cantor and supersets topologies the set \\(NP\\backslash P\\), if not empty, is of second (Baire) category, while \\(NP\\)-complete sets are sets of first category. These results are extended to different levels in the polynomial hierarchy and to low/high hierarchies, \\(P\\)-immune sets in \\(NP\\), \\(NP\\)-simple sets, \\(P\\)-bi-immune sets and \\(NP\\)-effectively simple sets are all of second category, if not empty. Finally, one shows that if \\(C\\) is any of the above second category class, then for all \\(B\\in NP\\) there exists an \\(A\\in C\\) such that \\(A\\) is arbitrarily close to \\(B\\) infinitely often. All results are proven constructively.","type":"string"},"datatype":"string"},"type":"statement","id":"Q688157$987306F1-C2C1-42E8-AA9E-763BD283E6DA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688157$1D581C74-EF9D-4E40-B125-0BB31FEDEE60","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"713eeb005fe25e721b847f73601f45e1ebac3fc3","datavalue":{"value":"440333","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688157$6F4B6DAA-8188-4ECE-BACA-BEC7305539A7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df1fb4eb6bcbfb2401661f7a0db39d11c1a5c5f3","datavalue":{"value":"polynomial computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q688157$ED87F700-2FCD-4CFF-BF63-0A59F9B64E7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e4aa9967ed6719814bbc09fbf5635711fec03a83","datavalue":{"value":"Cantor topology","type":"string"},"datatype":"string"},"type":"statement","id":"Q688157$086DA835-FB9D-4F1A-A215-16F37EA4891A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3cf176f8b744c069b8e584b9c0c177157000728c","datavalue":{"value":"superset topology","type":"string"},"datatype":"string"},"type":"statement","id":"Q688157$E752A009-B608-4D84-ACA3-BBF9F5BEF34D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b5564a54f7a1db96a5c633be8c0af63b0086b92","datavalue":{"value":"meagre set","type":"string"},"datatype":"string"},"type":"statement","id":"Q688157$F92074C2-B1BA-4515-BDFF-8C73CDBE7212","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"21fa9a9223cebca47884c37548205488b3400e7b","datavalue":{"value":{"entity-type":"item","numeric-id":235567,"id":"Q235567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688157$2D7B74C2-4C00-4227-B4FB-DA6FE00929A9","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":"Q688157$F5FB1303-CAFE-45D9-895E-A64D54439CBD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8e8c30651594c1eb9c8a2e2ed6c4a6e32cf1c7f","datavalue":{"value":{"entity-type":"item","numeric-id":4732106,"id":"Q4732106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688157$8CBA5E2D-017F-4A7E-8ADB-BC9DE8F59529","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a73e9dd505a59ae916afd9db654509c7207b51f","datavalue":{"value":{"entity-type":"item","numeric-id":4723714,"id":"Q4723714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688157$8428C740-0EC5-4E04-AB76-7769D60FCA2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cffbf4f835aa5098d423c3d5d378b9a5e8d9619c","datavalue":{"value":{"entity-type":"item","numeric-id":3683534,"id":"Q3683534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688157$545CAF78-3E19-4D67-BCE0-47D84F295A4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f498b4b27916cb2754d9411bcb8a15fcc27cc3b1","datavalue":{"value":{"entity-type":"item","numeric-id":1051633,"id":"Q1051633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688157$10BFAFC2-AD97-4E01-AB29-BD60C4EB5242","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd4f9b219f54da4cc88e481211745b7b70548f30","datavalue":{"value":{"entity-type":"item","numeric-id":4039803,"id":"Q4039803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688157$A55C9016-30E4-4716-9F2C-F255C2F9A7B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b77c359d113f74e32b5b8b8a0ffee20f29b60e6","datavalue":{"value":{"entity-type":"item","numeric-id":3690222,"id":"Q3690222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688157$AE81A37A-0729-450F-A2B1-F703DD2275F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae684093583dee05b426beb8dfbc38f72a5a5833","datavalue":{"value":{"entity-type":"item","numeric-id":3958443,"id":"Q3958443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688157$FE3F6B2C-4ABA-4D69-A1A2-F5DB079E3113","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a76d91d3dd1208426b047130d39894bfab628f04","datavalue":{"value":{"entity-type":"item","numeric-id":1210716,"id":"Q1210716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688157$FA4CE604-0857-45E6-8360-A6B399428884","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"648af4444efef3dfface63422920536bd2b0c180","datavalue":{"value":{"entity-type":"item","numeric-id":3928246,"id":"Q3928246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688157$E6976F8C-5137-4CE2-BCA2-1BD720B2D5FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0901ea37e028e397625252c5e0077ce0a338396","datavalue":{"value":{"entity-type":"item","numeric-id":4431223,"id":"Q4431223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688157$CFE84F91-7D5B-41B1-8D8A-403FE7CF016F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"862ea219c4a9b44f1c3bb448b0cf228839a066cb","datavalue":{"value":{"entity-type":"item","numeric-id":1071500,"id":"Q1071500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688157$5ADD9F3C-22A6-492D-9C1A-76242559F6B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c3412e57bd55dfe3981a5171c29889032839307","datavalue":{"value":{"entity-type":"item","numeric-id":3801071,"id":"Q3801071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688157$2DBEBCAA-B664-4865-BAB8-50FA4065D7E7","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":"Q688157$DB0AF3F8-5F5F-47E1-911B-8FDE5D460FC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2afbf85b23c2b0c24d5354dd68aca07c552d2026","datavalue":{"value":{"entity-type":"item","numeric-id":3495645,"id":"Q3495645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688157$61CA2493-6CEC-42D5-9607-3B5316A3C160","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9635365b0780328d7ae22bc69b462e7144999d03","datavalue":{"value":{"entity-type":"item","numeric-id":5573961,"id":"Q5573961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688157$85281FF6-AA5C-4222-A387-A6EE34B426FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44ff2c269b97a88de0fe652e2add75347876b7e3","datavalue":{"value":{"entity-type":"item","numeric-id":1361890,"id":"Q1361890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688157$A9186AE7-3DE0-4E06-9593-BB7E76896175","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a830cafef1f2c438cb7e2286bda476de992419e","datavalue":{"value":{"entity-type":"item","numeric-id":1052097,"id":"Q1052097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688157$11FC45EF-E537-4DC9-85EC-E066DDF742AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8bde708178fd22b5a6473ace4f76c9d9acbc0b80","datavalue":{"value":{"entity-type":"item","numeric-id":3347296,"id":"Q3347296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688157$BCF4A683-5AC4-4CE9-AC14-58E7D44DC849","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15736a1fabe53e34c9adbd1c3f77269c133e2124","datavalue":{"value":{"entity-type":"item","numeric-id":4040892,"id":"Q4040892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688157$78EB8201-C536-4205-8577-DCC7CB6B7999","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"68696eeef0daa12bd7a7b565a650992bdd6b4755","datavalue":{"value":"https://doi.org/10.1016/0304-3975(93)90161-l","type":"string"},"datatype":"url"},"type":"statement","id":"Q688157$E821B5FD-9D29-4884-A557-B5D949C805DA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"aaab29aea51f96e12b29a67f4c86a6f5fa9bf93e","datavalue":{"value":"W1969182601","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688157$92265756-5250-422F-8C08-0C0ADDB8D2A7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b7c947fbc9334d0d0b117d76c5d4e5949df6b4e","datavalue":{"value":{"entity-type":"item","numeric-id":672460,"id":"Q672460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6cfeecee9c7d1b36a3f9401e51f2dee7ec7f815f","datavalue":{"value":{"amount":"+0.7916203141212463","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":"Q688157$44F4F1D7-016C-4A85-891A-FDE6DCD2088F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c321227ef9aff13cc8f9f7cdd81acc7dc0ff0b0","datavalue":{"value":{"entity-type":"item","numeric-id":4841303,"id":"Q4841303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0b590e9d45c2999bc026ee16ba16aa3efa0b6c6","datavalue":{"value":{"amount":"+0.7731350064277649","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":"Q688157$D57C29D0-2F38-4B49-BA3D-053385368385","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"170cdb3aba648cfbc9313250beabf51cfbb4ab92","datavalue":{"value":{"entity-type":"item","numeric-id":5929911,"id":"Q5929911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c368daad4a68679d43e3ec5bcc3924d7db65c75","datavalue":{"value":{"amount":"+0.7713413238525391","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":"Q688157$16F96D2D-72DE-41C9-A184-8B8E3CE31B9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c081bc85bd567f684abbd79f813e3f8ca34b2c1","datavalue":{"value":{"entity-type":"item","numeric-id":4866587,"id":"Q4866587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4fbbde683ae38fa133884921a229b8a397cb4e5","datavalue":{"value":{"amount":"+0.7698000073432922","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":"Q688157$71CD5382-05ED-4CDC-A5F4-79312561239B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0f0d6cc3ce78984880e8defea4836c9fa711081","datavalue":{"value":{"entity-type":"item","numeric-id":3754606,"id":"Q3754606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1f37a5c2b527c3b08db4aafc36b1d4e360dfdc5","datavalue":{"value":{"amount":"+0.7592681050300598","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":"Q688157$64268975-F94F-4E31-9FF7-4152318090EE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"If not empty, NP-P is topologically large","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/If_not_empty,_NP-P_is_topologically_large"}}}}}