{"entities":{"Q1098837":{"pageid":1109589,"ns":120,"title":"Item:Q1098837","lastrevid":70626267,"modified":"2026-04-13T15:49:11Z","type":"item","id":"Q1098837","labels":{"en":{"language":"en","value":"Some observations on the connection between counting and recursion"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4037836"}},"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":"Q1098837$1B275BF8-E59F-4297-AF4E-9F39AA0C026E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d2b2e2332fff6c0a2a99b0a73d622e4e24eb16cf","datavalue":{"value":{"text":"Some observations on the connection between counting and recursion","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1098837$CB443B41-4CED-400F-B6CA-FF6090046B17","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6a86d1f912bb19fca069c2f0027a9d64296b9303","datavalue":{"value":"0637.03034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098837$CB12E6C5-CA93-4C4B-8366-0963D284CEE4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ec8e67922171d3a1248a21cf7fdb1401335c4bf4","datavalue":{"value":"10.1016/0304-3975(86)90141-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098837$80E3135B-A589-46C9-85A9-48E4055848B2","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":"Q1098837$473A43E3-3A0D-4AFB-BCE2-D51FB8BA1E16","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":"Q1098837$CC935978-10C3-456B-90B1-6B1D676218B6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8b73e68d728c4b1b8f6d463ebd49c2cb5510bd6b","datavalue":{"value":"Let {\\#}P be the \\textit{L. G. Valiant}'s [ibid. 8, 189-201 (1979; Zbl 0415.68008)] class of all functions counting the number of accepting paths in nondeterministic polynomial-time computations. The author introduces the polynomial-time hierarchy of functions by defining 0{\\#}P\\(=P\\) and \\((k+I)\\#P\\) to be the class of all functions counting the number of accepting paths of nondeterminisitic polynomial-time machines which have a function from k{\\#}P as an oracle (thus I{\\#}P\\(=\\#P)\\). For \\(PHCF=\\cup \\{k\\#P:\\) \\(k\\geq 0\\}\\) the following inclusions take place:  \\[  P\\subseteq 0\\#P\\subseteq I\\#P\\subseteq...\\subseteq PHCF\\subseteq PSPACE.  \\]  PHCF is shown to be coincident with the closure of the class P with respect to the operations of substitution and summation. The class PHCF can be generated from the basic functions \\(\\{+,-,\\cdot,:\\}\\) by substitution, weak bounded primitive recursion and weak product (weak here means ``up to the length of the argument on which the recursion is made'').","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098837$97B27996-12CB-4B18-A145-8DF59561C309","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098837$217F2523-4E0C-4302-B8EA-301735F14CED","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"53960441607d2cbc263392d037462bfdc2d9e544","datavalue":{"value":"4037836","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098837$617AD954-86E9-477E-B688-7B7D21DF2CA4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c323b73cf8960adb039507dd3d53e7d1488e6670","datavalue":{"value":"counting functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098837$888C24E6-3487-4DD0-8122-A9F930915B3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae85d4ac5aa0b4212aff6e6543148184fe814ded","datavalue":{"value":"accepting paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098837$F771EFA2-0FF9-42A4-AEE1-16076872AB42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c570c484dde01cd6d2c578b720c57eb43ce6cfb","datavalue":{"value":"nondeterministic polynomial-time computations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098837$C7E83190-E086-4715-99F4-A1AD0BE18208","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdccdf568e70f6da8a9c1a7493cf8878099fb20e","datavalue":{"value":"polynomial-time hierarchy of functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098837$B750ECE7-F297-4F29-A2D7-1AD9769547E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac873341ab34d6db98676ef037e18583cae25841","datavalue":{"value":"oracle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098837$5773A248-9139-47CB-A43C-1ED62FD6FED4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"05ccf9363a2b93804ef06018f3f40241df688bac","datavalue":{"value":{"entity-type":"item","numeric-id":675063,"id":"Q675063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098837$4EB72974-1B8F-4BC9-9093-56D01D774B2E","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":"Q1098837$AF1E47E4-DBBF-4CED-BCA5-D140AF2478E8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"41e1ddcaf8df6de181107d9c941dc7612f5cf73b","datavalue":{"value":"https://doi.org/10.1016/0304-3975(86)90141-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1098837$EBD0ED28-B608-4996-8122-7FDFD65EB874","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"691e7f27160e9319e1452d3381b6ba93ded87ddc","datavalue":{"value":"W2002385864","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098837$6FAC7B3D-86F7-41C9-AD45-92A15CE34CE9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"66eb6cafceb6ff937706546e940b98bf1f012a63","datavalue":{"value":{"entity-type":"item","numeric-id":1171880,"id":"Q1171880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098837$77787E2E-5BC7-4159-88C2-0889A4D758F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb71ea59fd47b573033df9513037924711bc7127","datavalue":{"value":{"entity-type":"item","numeric-id":4062633,"id":"Q4062633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098837$69667A6E-2288-41FF-9CE6-9F9142B28ED5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"569fa9c504c5ecc928a3de3b9e903ccaa7770887","datavalue":{"value":{"entity-type":"item","numeric-id":1057267,"id":"Q1057267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098837$3EAF7AA6-7B24-49EF-BAC5-2C374B09FA62","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":"Q1098837$D1AA6278-F304-4605-91F7-48F5528DAF0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cee115f650dd9b2c9350f8cdefbe2dab8f0e067","datavalue":{"value":{"entity-type":"item","numeric-id":5824357,"id":"Q5824357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098837$7F205D00-C764-4D25-9F30-DE06A44DC59D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc518301a37d088fd4a4001340a0979eff2a0553","datavalue":{"value":{"entity-type":"item","numeric-id":5843849,"id":"Q5843849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098837$0BD72EFB-3E18-409B-9ADD-C319982CC603","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11fc8f5bb5704d3224b97e588e8093982d5aaed5","datavalue":{"value":{"entity-type":"item","numeric-id":1064780,"id":"Q1064780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098837$8491B74F-9AF5-4D1F-A141-133E74E0E7D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab289263ac80a8df854a0b026020c7e068e5240d","datavalue":{"value":{"entity-type":"item","numeric-id":1052094,"id":"Q1052094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098837$86C22A08-6519-4BF7-B58E-EB37FD59323B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48aa19dd4b3d3f987b8cfe767c8911e74709e4ec","datavalue":{"value":{"entity-type":"item","numeric-id":1237361,"id":"Q1237361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098837$7EDABC8E-C40E-46C3-BB69-BD6FCBC8091A","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":"Q1098837$2892514D-9883-4DBB-8D4D-34E2CFC550D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2146e12d70096585412fa50f364e0fbe43b7e82d","datavalue":{"value":{"entity-type":"item","numeric-id":3293402,"id":"Q3293402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098837$2B4A0155-F14F-4925-AE6C-6C9E7FAFC792","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dfd289a1de1a37145d6ea9a295c67e5dcd55ea50","datavalue":{"value":{"entity-type":"item","numeric-id":4139697,"id":"Q4139697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098837$F9BF0459-C8E9-4278-82E0-2BE70FEE0B8A","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":"Q1098837$079C0AE0-E1BF-4F7B-A889-8A768DE2D80A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf1ecfd40a40c1bd2742231bb57c108e7536fff2","datavalue":{"value":{"entity-type":"item","numeric-id":5637881,"id":"Q5637881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098837$7341D6A8-D9B6-4B4D-9147-22848E18C13C","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":"Q1098837$AE435EE1-5B42-4E54-B2FA-FC7B4F907DEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70536879af054717c0f3d9d913a10e93c328980d","datavalue":{"value":{"entity-type":"item","numeric-id":3853129,"id":"Q3853129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098837$CB87EE94-FE38-455C-9E2D-74FDB64B22D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66e59de626f429fbb6c2fca3abb0f5a6a209ade0","datavalue":{"value":{"entity-type":"item","numeric-id":4196412,"id":"Q4196412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098837$EB85C636-5930-4D49-A890-CC635E59A2DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85cad89a6a097b4ba9f4404e7ae0ffefe8357882","datavalue":{"value":{"entity-type":"item","numeric-id":3217604,"id":"Q3217604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098837$46DB88C5-986E-4DCE-925D-987B644AEDA1","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":"Q1098837$A5553408-7FEE-4A5B-B4D9-FCD8B6D3C870","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"656a88094d3818a28a699dfaea22a6fc84ea05fc","datavalue":{"value":{"entity-type":"item","numeric-id":3707407,"id":"Q3707407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098837$EBFC4681-537E-4654-99E0-7D09D3F58514","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3b34bb9d2a377ee4a9cb6a77b8dd9a28b536708","datavalue":{"value":{"entity-type":"item","numeric-id":2085583,"id":"Q2085583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"010fd43f9283d80730dc95c91918e27a91a92cdc","datavalue":{"value":{"amount":"+0.8496267199516296","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":"Q1098837$38FE4906-870C-4210-8031-D132512B5D64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94380e8fb539b78e1d43e893fb36b268c37b3ee7","datavalue":{"value":{"entity-type":"item","numeric-id":3990656,"id":"Q3990656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1310446843296483d829c9f6de97d7099beb8df6","datavalue":{"value":{"amount":"+0.8346621990203857","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":"Q1098837$7F6C2BDA-2575-4F6A-AD0A-6D7699078D11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"187edd84811e0420aaac0b5c008e1df70f66181a","datavalue":{"value":{"entity-type":"item","numeric-id":1365942,"id":"Q1365942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72b824790191094431d6689b02c8ff589596e1e1","datavalue":{"value":{"amount":"+0.7978068590164185","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":"Q1098837$BD43BCA9-32CC-4B93-96A5-1613454CC9DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1433c5681faf4e64988f74cfac985d8917e4423","datavalue":{"value":{"entity-type":"item","numeric-id":1337389,"id":"Q1337389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c0eb0f17771ca7711248acf67e469175cc57c2c","datavalue":{"value":{"amount":"+0.7636682391166687","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":"Q1098837$A1AE610C-A471-40D4-A4F8-E9933F6C7AE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45bfbd0453cf7b48d9491b4811ec739ec60088f2","datavalue":{"value":{"entity-type":"item","numeric-id":1199550,"id":"Q1199550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3acf8c22dcae7ed521df909dd0164e58605dadf1","datavalue":{"value":{"amount":"+0.76337730884552","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":"Q1098837$8F09B5EC-216E-49A9-82A7-B49060C57A30","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Some observations on the connection between counting and recursion","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Some_observations_on_the_connection_between_counting_and_recursion"}}}}}