{"entities":{"Q795035":{"pageid":796883,"ns":120,"title":"Item:Q795035","lastrevid":64394955,"modified":"2026-04-11T19:34:10Z","type":"item","id":"Q795035","labels":{"en":{"language":"en","value":"Polynomial time computations in models of ET"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3861133"}},"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":"Q795035$4F668651-DF3C-4132-8371-7DBDBA48E64A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ec1a413fe04482eee23835cdc0c7e944cf94e8d9","datavalue":{"value":{"text":"Polynomial time computations in models of ET","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q795035$9F758527-6F6E-4B11-8AE4-9DE11FF7F0C6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0a504a7ad965f0bc259661dd5f7d907e4f8b9887","datavalue":{"value":"0542.03019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795035$787BD137-E949-4E71-AAD1-7DACB7D1A911","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"974548b6759d89888e829ae4a268e95fd9f060e2","datavalue":{"value":"10.1016/0022-0000(83)90004-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795035$251EAB02-957C-402D-BC6A-F38AC02B7826","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c694d2ec8772adea9a7a0a2fccea6fc581e7b34e","datavalue":{"value":{"entity-type":"item","numeric-id":687509,"id":"Q687509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795035$F2B88D1D-E8FE-4DE7-AC38-8BDB78F67BE0","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":"Q795035$E35A21DB-4938-4E63-A9C7-8D2A3D0F2CFC","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":"Q795035$F8D24C5D-C21F-4420-8F1F-88CFE9FA857C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"436cbad69a23c815e949d2cd13b51ce0189d3381","datavalue":{"value":"https://hdl.handle.net/1813/6340","type":"string"},"datatype":"url"},"type":"statement","id":"Q795035$3649746A-C5D8-4679-AA69-AA0110897E92","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"552503a0b89cd58589ec40f3f312e1365a72d4a9","datavalue":{"value":"The paper is devoted to the study of the P\\(=NP\\) problem. The theory ET (theory of exponential time) introduced by R. A. DeMillo and R. A. Lipton in 1980 is studied. The author discusses polynomial time computations in models of ET and gives examples of simple functions that are not total in \\(M_{D\\&L}\\vDash ET\\) as well as predicates in \\(P_{D\\&L}\\) (a class of predicates over \\(M_{D\\&L})\\) that are not computable in \\(M_{D\\&L}\\). The stronger theory ET(Elem) is introduced and sets that are polynomially computable in some model of ET(Elem) are characterized. The last section of the paper is devoted to the following problem: what types of hard sets have arbitrarily long initial segments that can be efficiently decided by short programs. It is shown that it is easily resolved for P and EXP-time complete sets. The question for NP-complete sets is open.","type":"string"},"datatype":"string"},"type":"statement","id":"Q795035$52846542-6634-4882-BF44-743EDDE2E21F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795035$1E90FA81-B61B-4C0F-9C49-889DECAE8343","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a22eb1f642cbb79777784e33676c61b720925aab","datavalue":{"value":"03H15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795035$4E1A752D-7B24-41A7-81E3-553F8811239A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b0892fc31accf84a9a1151504c6a92e44069b352","datavalue":{"value":"3861133","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795035$EF6D2DDD-8E86-4752-912E-378A2FDD0975","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4f2891ec95ee556b0ac2cc2dddee3d77811bd94","datavalue":{"value":"computability","type":"string"},"datatype":"string"},"type":"statement","id":"Q795035$0D568CA5-63F8-4D16-B20A-B1A0F4700459","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ba63dcda64409670e8f0f2c533efdbfa1e0ce84","datavalue":{"value":"\\(P=NP\\) problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q795035$1C422F89-015B-4326-8B3B-7C1FB60B0435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0536360aa81dff853b7ec1ab1405b41f6891de3","datavalue":{"value":"theory of exponential time","type":"string"},"datatype":"string"},"type":"statement","id":"Q795035$DEF81397-D0C9-4E75-91F0-19B9BCBB7FAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb49ebb629786f49e8d7b2785ade14f8bd21bddc","datavalue":{"value":"polynomial time computations","type":"string"},"datatype":"string"},"type":"statement","id":"Q795035$B743525B-5ADE-48EA-885D-E41B274F3492","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01653852dfe5926b425173de4d262536a3628b14","datavalue":{"value":"hard sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q795035$24FEF2AB-81AC-4B26-98FB-7B40431B062F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"002d1492e7a86c4a2239a4de6d010ee6cd1f5cdd","datavalue":{"value":"initial segments","type":"string"},"datatype":"string"},"type":"statement","id":"Q795035$01F0F95F-A6C6-4579-9444-7B1F1F85DB9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee7be3faea7ff556f215b9e45b975045d6d5fb75","datavalue":{"value":"complete sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q795035$66A18CDD-BF19-45B9-AFEB-45B7F661851D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c45938d3b1c1a5c68183caabb02f42934d9ff682","datavalue":{"value":{"entity-type":"item","numeric-id":588140,"id":"Q588140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795035$C1A99E9F-CA93-4DB4-8406-951DC05A9B27","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":"Q795035$AAE48F0C-5E59-4026-AD3C-674351EFA7D3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3d816c7986896e4a98858f7686b2365bc53a6829","datavalue":{"value":"W1985249556","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795035$0E6A7A9C-18CC-42BB-8BBE-76D3D4F56A2F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"45543575358fa9f936229ea1980f01498db37989","datavalue":{"value":{"entity-type":"item","numeric-id":4128010,"id":"Q4128010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795035$67D84269-5E96-4B99-A4C6-81FB59CCABA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1fb329ed3fd0a0f916dbd8faa97acee5cf8861c","datavalue":{"value":{"entity-type":"item","numeric-id":5183082,"id":"Q5183082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795035$0C4F2628-F125-4AB5-B521-FA270BDF5683","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a6e1aedacd158f689a2f10e6f01952732faca22","datavalue":{"value":{"entity-type":"item","numeric-id":4198488,"id":"Q4198488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795035$9E1A16BC-6051-4B09-9A5D-43EE31B90488","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82fe1700ff97e6850bd8ab19a07be4ba1db7a677","datavalue":{"value":{"entity-type":"item","numeric-id":1158957,"id":"Q1158957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795035$79410B37-31C2-45DE-941F-F41F9501E312","rank":"normal"},{"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":"Q795035$3CA08C36-22C6-4CD2-BA0F-3DBF6774943F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40c62062de7837e74980976f9ffd2b1553f5599b","datavalue":{"value":{"entity-type":"item","numeric-id":1140080,"id":"Q1140080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795035$ADF4FF7B-7FD3-4203-A5AC-4F18F6E97C5D","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":"Q795035$F821CB11-DCF3-4F16-8D06-9AB7AF215206","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ece2270b16b9fbc48e0a9ac072c1cea045ecd584","datavalue":{"value":{"entity-type":"item","numeric-id":1162811,"id":"Q1162811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795035$BFE78702-F888-41CC-9669-69324BCAAED7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c695379422b7047c66b9db17e8a4509aa87bc9ee","datavalue":{"value":{"entity-type":"item","numeric-id":1162506,"id":"Q1162506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795035$FB2DE1F1-1E00-4840-AF42-9E84FE3738D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"704b67c0c7a5a44ff323d18e1363803acffd4565","datavalue":{"value":{"entity-type":"item","numeric-id":4071737,"id":"Q4071737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795035$7D53507A-8721-4B5A-9B83-34743EC21277","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21c346fcf8c23cf4fedee6adca5eb2e9b1b265a3","datavalue":{"value":{"entity-type":"item","numeric-id":3887444,"id":"Q3887444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795035$1143A969-00DA-4932-8570-182686BBEBF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c059d1355bcb0df592c7e924663d48f24f3b387e","datavalue":{"value":{"entity-type":"item","numeric-id":5613949,"id":"Q5613949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795035$F1E136D2-0C45-4EE9-8861-491EB53F183F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d036cf14ecd1c21ee7bc33fb4e75ac50e627457e","datavalue":{"value":{"entity-type":"item","numeric-id":3941393,"id":"Q3941393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795035$BBD52EA5-FD13-4C99-944D-CCCB60382F5D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81c4559f05230f57df55d0391b2fee807801060f","datavalue":{"value":{"entity-type":"item","numeric-id":3476273,"id":"Q3476273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96822a6e12e5e023b6ad873a506bc91367a2ca45","datavalue":{"value":{"amount":"+0.7503482699394226","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":"Q795035$00DA4B55-2E2F-4BC7-8572-B03501605ED5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0cc305899532778e84bc1624fb79491ed8528098","datavalue":{"value":{"entity-type":"item","numeric-id":3759938,"id":"Q3759938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb18e0de30c51bbe5f9313b46bc801700447045d","datavalue":{"value":{"amount":"+0.7438100576400757","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":"Q795035$E98F7474-616C-48A4-8692-AE600A3247CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d14a1ad3832c6aa45fbe86ea2ff94ca3a5ab8a2a","datavalue":{"value":{"entity-type":"item","numeric-id":3835449,"id":"Q3835449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e62daed1dae49d22c8ffcaf7aecfbba98c1c2775","datavalue":{"value":{"amount":"+0.7314302325248718","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":"Q795035$7280BA9F-2FB5-48E8-87A1-A6ECF0FF611B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b38698410b10d1b605e95efd4de66bd5ba470a8","datavalue":{"value":{"entity-type":"item","numeric-id":3484825,"id":"Q3484825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e77943751c542e68be87106b8d855b39587d3527","datavalue":{"value":{"amount":"+0.7303080558776855","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":"Q795035$7673AD2E-0AA5-4EF3-9FF5-ABD1395B2E29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1526ebe85befb8ff6fd594f83cb5badb7361965f","datavalue":{"value":{"entity-type":"item","numeric-id":1327386,"id":"Q1327386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e87aee7ca1a112d14fc3cff12b9446808506637","datavalue":{"value":{"amount":"+0.7302321195602417","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":"Q795035$F10A635E-4985-499C-8DB9-848831C61471","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Polynomial time computations in models of ET","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Polynomial_time_computations_in_models_of_ET"}}}}}