{"entities":{"Q1190987":{"pageid":1201736,"ns":120,"title":"Item:Q1190987","lastrevid":69856974,"modified":"2026-04-13T10:48:43Z","type":"item","id":"Q1190987","labels":{"en":{"language":"en","value":"Turing machines with few accepting computations and low sets for PP"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 58809"}},"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":"Q1190987$DA876306-DDA3-439C-86CE-3AD24A39FA53","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e9f59059b26b8029f51988de3ae836e8418d3048","datavalue":{"value":{"text":"Turing machines with few accepting computations and low sets for PP","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1190987$F5B9B6D0-226C-430D-B19F-84C50D4F6C1A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"25f5d0d9b594e1861d1e55f78742da23376f52f1","datavalue":{"value":"0757.68056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190987$98EDF158-82D5-4B5C-8BE0-9AD1FD920327","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fada41c3d3925956ae4444703bfc266b04ec8278","datavalue":{"value":"10.1016/0022-0000(92)90022-B","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190987$F3C3E159-1852-4AD3-A19A-C8E785CEB825","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ccdbbd400f0c973fa2e979fe6e13986f59d9284","datavalue":{"value":{"entity-type":"item","numeric-id":259078,"id":"Q259078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190987$2E133A29-B772-47C1-BB6D-AB7DC4C61779","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"98e020d336f4040f2344877fb27890751f480383","datavalue":{"value":{"entity-type":"item","numeric-id":1052096,"id":"Q1052096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190987$7656D21B-2A50-4D3A-8D5D-9A6EFEA76B80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"efa0ee16bcf9d62945fa4e27ea47d07c341ed7b6","datavalue":{"value":{"entity-type":"item","numeric-id":1114674,"id":"Q1114674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190987$D04E9403-A676-4454-8938-AC44303AEA0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b46006266dfa27f78f67dac26590ca028f0108a7","datavalue":{"value":{"entity-type":"item","numeric-id":6482543,"id":"Q6482543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190987$2603B476-54B7-487A-81F1-9080F4F7F46C","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":"Q1190987$C0A59DF9-B02D-42EB-AE47-27A2BED4571B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5fd62271fe98c7ff9916cafed51cf35315eeeb31","datavalue":{"value":{"time":"+1992-09-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1190987$C0AF4AFC-D704-47ED-BAD6-AA2149C5D355","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c9f5d97f92fb7bbd9b1164fbaedea54791469980","datavalue":{"value":"Complexity classes, defined using the idea of bounding the number of accepting paths of a nondeterministic Turing machine, were introduced with the hope that perhaps they represent more tractable subclasses of the class \\(NP\\). The paper investigates some properties of the path- restricted class \\(Few\\), which includes also other known classes of this type, i.e. \\(UP\\) and \\(FewP\\).    It is shown that for every language in this class there exists a polynomial time nondeterministic machine that has exactly \\(f(x) + 1\\) accepting paths for strings in the language, and \\(f(x)\\) accepting paths otherwise (for a polynomial time computable function \\(f\\)). This result is then used to prove that \\(Few\\) is low for the complexity classes \\(PP\\), \\(\\oplus P\\), and \\textit{exact counting}, i.e. an oracle from \\(Few\\) does not increase computational power of machines from these classes. Lowness for \\(PP\\) is shown also for sets from the class \\(BPP\\) and sparse sets in \\(NP\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190987$03E70932-F007-4B37-AA20-D24A3410960A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190987$DA72A6F9-B2D1-4E80-BC27-95B948C1F951","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190987$EF99CA03-FD8F-4D2E-B30C-71F7C583AFD3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e82f4672d8e743788bacfe4990cb8c5343f9e69b","datavalue":{"value":"58809","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190987$9F10A15D-C210-4D92-9141-A1317B4F6F4C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca0db7de20841d423e158436bb1451df4f7d13ee","datavalue":{"value":"low sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190987$50D27453-451A-4A6F-B2A5-B562D048A55B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06059c11269d258bbccac60c4e9a619d8f9e5b9a","datavalue":{"value":"relativization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190987$A62628AB-1656-4809-A187-E6EFCC7E1060","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27e1408d4ab83337d58920008ae37cbf7c29d257","datavalue":{"value":"path restricted nondeterministic polynomial time machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190987$61DC5C17-1553-44C5-8835-1D92975CD303","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4418b7d4f2a0250db5c25bb23e561efd56a43eb7","datavalue":{"value":{"entity-type":"item","numeric-id":587571,"id":"Q587571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190987$32EFB3FD-5964-4084-9C34-BD9E1C24FD9F","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":"Q1190987$F3CC2580-680C-4D8B-B232-DD2E00901C12","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"20dbb88399b28648dc9d78bc8b7f00777d16b9fd","datavalue":{"value":{"entity-type":"item","numeric-id":3028343,"id":"Q3028343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190987$1B2D9374-C889-4AC2-A0AF-88FBEEE04CA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab0bbeb503b6269a452e86ee83e6a8c71fdfdfd0","datavalue":{"value":{"entity-type":"item","numeric-id":3734382,"id":"Q3734382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190987$20BEB1F9-A821-403E-A457-AFD23070917C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51e8ca4fe98e898ca79eea259b27eebc5567af3b","datavalue":{"value":{"entity-type":"item","numeric-id":5096157,"id":"Q5096157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190987$536F82A2-0DD3-47C4-B9C2-BC9952680775","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb24dff4005148539085ff5c885035cfccaed69","datavalue":{"value":{"entity-type":"item","numeric-id":4140967,"id":"Q4140967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190987$4030E717-9719-4F9A-8999-0558CF0ADA94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b543b24a2524e76130d5c1525baa40aa9abdeef","datavalue":{"value":{"entity-type":"item","numeric-id":3675520,"id":"Q3675520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190987$FF08FFB5-F55B-4B33-8490-483D2B28D846","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6139d2fb76790fbc1a2ff20446f11785d8f1488","datavalue":{"value":{"entity-type":"item","numeric-id":1168733,"id":"Q1168733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190987$866C0F48-1987-41DE-A257-FB6DE9675EFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53e31dd483387e2770ec0ec431458678950cd036","datavalue":{"value":{"entity-type":"item","numeric-id":4743737,"id":"Q4743737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190987$DC7402E6-75B2-4F23-B163-646F02E5383D","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":"Q1190987$2A60BDB9-FAF5-451C-8B0E-8E41CFC6918D","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":"Q1190987$30539BE4-AAC6-412E-87F4-28F569DB5C6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b0ab4495987574a4e27adf88a7063c47cb1ef5c","datavalue":{"value":{"entity-type":"item","numeric-id":1186606,"id":"Q1186606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190987$389CCF6E-6B53-446B-A717-745C8E9359FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3fdeac57e6ae30181fb2db5f7f4e10e134e5670","datavalue":{"value":{"entity-type":"item","numeric-id":1232181,"id":"Q1232181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190987$ACD34FD6-2624-4EF1-92EC-7E7612EFC296","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68c516460706e34bfacf776c096f40a576fd2116","datavalue":{"value":{"entity-type":"item","numeric-id":600247,"id":"Q600247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190987$4F9E31CD-C849-4FEE-8D5E-D30C3CE7F931","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0e1c59b20b978e8e0de5a32fdeb6c212dbd6e1a","datavalue":{"value":{"entity-type":"item","numeric-id":1090455,"id":"Q1090455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190987$1FD99560-9DED-4DE6-AE91-EA6C3E4D369B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50e2a095ad948258628b96c48b26f673da92a690","datavalue":{"value":{"entity-type":"item","numeric-id":4725751,"id":"Q4725751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190987$7103FB33-D65E-4EE8-ACDC-FF9A05940C1D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c5e8e0cc89762c5e26d66c87a987ab5138723eca","datavalue":{"value":"https://doi.org/10.1016/0022-0000(92)90022-b","type":"string"},"datatype":"url"},"type":"statement","id":"Q1190987$48C89269-9182-43B6-AAEA-D29C3285A1C2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fae7e11e162cff70fc11ad2a470da0d9323cc5d6","datavalue":{"value":"W2178192088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190987$1C02DA70-7994-4EC3-96BD-190387526DF8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c1649192456cac16910e4ce1e137d2518765cec","datavalue":{"value":{"entity-type":"item","numeric-id":5750401,"id":"Q5750401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aeb3aae28c50f037b5ce016b899721ec58b96217","datavalue":{"value":{"amount":"+0.7981130480766296","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":"Q1190987$F84590CA-D210-4D19-B547-3A22B4E34E9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c92dc073392f70fdbc768d8360058da428043e49","datavalue":{"value":{"entity-type":"item","numeric-id":5096157,"id":"Q5096157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa79adc925764d26ae9d1a495c70fcbc37cee9fb","datavalue":{"value":{"amount":"+0.7931461334228516","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":"Q1190987$7326754B-E957-47B6-BB36-F8D2849A107F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8b7404769237d407fa3653aa348c6ab88e8b5de","datavalue":{"value":{"entity-type":"item","numeric-id":3359759,"id":"Q3359759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff41a865f5decc10c7ea70b3075b388c1d96bbe9","datavalue":{"value":{"amount":"+0.7880984544754028","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":"Q1190987$E2ABD906-1336-4B34-B830-0F01FB2CBE28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db4a30c2739a0b26d2b5fd766fc4332be5436ce1","datavalue":{"value":{"entity-type":"item","numeric-id":5896571,"id":"Q5896571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96487cce1f43600da15c375ef346194a5bfd6046","datavalue":{"value":{"amount":"+0.7702943086624146","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":"Q1190987$874A6C01-0F7D-4F75-99DB-A45B8401535E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca23cec0135d3e9a8f38040ca062aacb68d3fd92","datavalue":{"value":{"entity-type":"item","numeric-id":5905584,"id":"Q5905584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f369e5b701bc4389b86e9c140c4f564a33cfb14","datavalue":{"value":{"amount":"+0.7551136016845703","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":"Q1190987$479C2D48-60ED-4DFE-9614-4281BC200AA8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Turing machines with few accepting computations and low sets for PP","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Turing_machines_with_few_accepting_computations_and_low_sets_for_PP"}}}}}