{"entities":{"Q412210":{"pageid":413977,"ns":120,"title":"Item:Q412210","lastrevid":61658532,"modified":"2026-04-11T00:46:47Z","type":"item","id":"Q412210","labels":{"en":{"language":"en","value":"Faster \\(p\\)-adic feasibility for certain multivariate sparse polynomials"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6030307"}},"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":"Q412210$3D18340E-FFA1-40D9-9549-1CE3B10D72CD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ea9b4c8d3c080dda28a8e406a188428c9c639b28","datavalue":{"value":{"text":"Faster \\(p\\)-adic feasibility for certain multivariate sparse polynomials","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q412210$E35E13DD-2E7A-4591-86FD-A279CCB5A67B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c260f585ef49822b31e50c2f521729fda9056d06","datavalue":{"value":"1246.65078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412210$846020E9-B4E3-4B50-90B6-8CF4406B1084","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ea72303f92787da89554ee5fa15621068821a762","datavalue":{"value":{"entity-type":"item","numeric-id":99061,"id":"Q99061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$AE8B5238-EC78-43F0-A418-D27E12023223","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8d0f2e18c1df897dbb15de5492927d1ae63c4ec2","datavalue":{"value":{"time":"+2012-05-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q412210$710181B5-523D-44E2-8143-AC1044AD3C9A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e431f2f019b4b7aabb522d5dad0fcc318f8dec19","datavalue":{"value":"https://arxiv.org/abs/1010.5310","type":"string"},"datatype":"url"},"type":"statement","id":"Q412210$0D329607-0F4C-4661-AC62-4032C329DCC2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5f5416beb916581f75f5ab84beb89bb5ea5258fe","datavalue":{"value":"65H04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412210$3F6D585F-5C21-4FC8-94C4-6198629D05C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412210$B1CA9EEA-AD87-40AD-9F04-7AA798740BCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c9cf30409c08d8794814df406302eff616099c6f","datavalue":{"value":"12D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412210$C14812CC-2F87-475B-89BC-4AD04A7BCD7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"661c831991cdebd51f9465b74d929024bd00f373","datavalue":{"value":"12Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412210$1C420FD3-8287-44F6-924B-5113AEB3E8F3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5fde8d285b11877a15d878c01a86f1297e9656e6","datavalue":{"value":"6030307","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412210$DB0DA17E-25F6-4996-A79D-8097EF62021B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d107c8021cb7edf2bf3780a4c1d3754d63c5f3a0","datavalue":{"value":"feasibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q412210$AD3FB6EA-2B81-4738-92D8-AF2B95D74DB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b39c3e23f9a83da53e4b8a0555421e5f30d22ff7","datavalue":{"value":"\\(p\\)-adic rational","type":"string"},"datatype":"string"},"type":"statement","id":"Q412210$703C22A3-0667-4127-9E7A-5FEECC7DC79E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"041ddd04d9431b32353aca37a13f94e68ca329be","datavalue":{"value":"fewnomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q412210$B67A6501-A990-4459-BCC7-73D14B1C4FEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q412210$7BA84080-4A19-4010-B50D-2A4667C593DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7589e5c0a1d6cd20bae4e6d7b12fbe0a5f072c56","datavalue":{"value":"short certificate","type":"string"},"datatype":"string"},"type":"statement","id":"Q412210$D5DFE91F-4497-4C16-B76F-E3A4A14C674F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q412210$B7808308-DA80-43F4-8BDC-5B99976FA72F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fecaf2cdd9ebb1485464cb18f4be88ddaeb18f0b","datavalue":{"value":"sparse","type":"string"},"datatype":"string"},"type":"statement","id":"Q412210$3B7AD5AC-8F8A-41D2-8FFA-4B27D830D718","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93783073cb9fe7fb382ff90959747bac58c4e709","datavalue":{"value":"trinomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q412210$011670B1-14AC-45AC-8FA5-DFED10B02535","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"914b4455cd1a2520c4bd4dc41e844fbc1006e353","datavalue":{"value":"multivariate","type":"string"},"datatype":"string"},"type":"statement","id":"Q412210$C7F44B18-3819-43BB-8044-ABD6068008D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"addee7cb1297443e3bb059e51167dfcab10fa3d9","datavalue":{"value":"Hilbert's Tenth Problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q412210$A9B35073-05F4-48E1-9556-141F123571E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4cae7f273b8221f498b4fed403b7f14ed86a07d","datavalue":{"value":"Newton polytope","type":"string"},"datatype":"string"},"type":"statement","id":"Q412210$7BF9837F-86CF-410D-BD4C-A79EA11A4B5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9a77a12b6551397f0189eaddbe6bea049546266a","datavalue":{"value":"Laurent polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q412210$2D65D8D0-CE5E-460B-8B98-DE66F25F6062","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63d2412a4b168c2728b1aae3a7824f35027bab33","datavalue":{"value":"Hensel's Lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q412210$49B5DDBD-25C3-425F-A3D0-0B5B4A27FBE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe1f6d1a57ddcefc8011159d7310d5d67c92bf11","datavalue":{"value":"Wagstaff Conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q412210$D7B12717-42EE-4D5D-BC4D-172CFE1D0406","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2e22ab0741fdf8f80fb8436ed92baf31f66960bd","datavalue":{"value":"\\(p\\)-adic rational root","type":"string"},"datatype":"string"},"type":"statement","id":"Q412210$9A61C2F5-0BE5-44AD-B2E4-E85794A6B940","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4f216bf5315f119cd6b8e6e21478a01c8d73dc22","datavalue":{"value":{"entity-type":"item","numeric-id":1264427,"id":"Q1264427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$65F8FADB-A6AA-48EF-82E3-A6EB059F3460","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":"Q412210$16698608-E9A4-4B3D-84CC-0C7BDD5B28D1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ea2c6d6a0dab648475d87337c49c6bb28f1c0c20","datavalue":{"value":"W2963445336","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412210$08BB63B1-2CCD-4CFC-A4AF-2D83D4027D7C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1234570f11caddb900135131d2fd06479f5792ac","datavalue":{"value":{"entity-type":"item","numeric-id":1772458,"id":"Q1772458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$38CAE848-218A-466E-B9B7-C499C226F272","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84233bbc6847c2e185b284cf773f2002c25b0098","datavalue":{"value":{"entity-type":"item","numeric-id":1334322,"id":"Q1334322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$FEA500D4-9D5D-4202-891B-4E7C1B7EDA09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71c4c747ce6c000eacdccddf5ed6a23704e599a2","datavalue":{"value":{"entity-type":"item","numeric-id":5522902,"id":"Q5522902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$26D590AD-879F-4B4B-8D4F-373977BC3C20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1b645cefad6f2b06d317aed1455876ad9997db3","datavalue":{"value":{"entity-type":"item","numeric-id":3105508,"id":"Q3105508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$6BD54BB6-8E09-458E-BECC-EAD5D3BDC3AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88d346d7362f6dd5bd49046a1ac8df163429da38","datavalue":{"value":{"entity-type":"item","numeric-id":5510996,"id":"Q5510996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$F62D6795-55E4-4EA3-A16E-E4C121D7D98A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a93f13262bc300fba769190aafdb0940400641e6","datavalue":{"value":{"entity-type":"item","numeric-id":4888749,"id":"Q4888749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$FC3D55E5-D328-4BFA-A544-F25009260217","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09562100b7bc7593a9a3a02d141657cd5f16f798","datavalue":{"value":{"entity-type":"item","numeric-id":3105516,"id":"Q3105516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$DBD40E0B-95EC-439E-B6C5-D6B5D96B8282","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fb1e069c9e4331b31c569dc8e2183f4c63cb5ba","datavalue":{"value":{"entity-type":"item","numeric-id":5920628,"id":"Q5920628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$690C9ECB-3614-4648-A417-0E3789659AC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"217f829da18444c1151609ce0c79a556bddb15f4","datavalue":{"value":{"entity-type":"item","numeric-id":2883798,"id":"Q2883798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$7865B793-CA80-4A68-94D2-2C1B6AACF663","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76286cf28a16befde86e907a21f1ad97c9e2c809","datavalue":{"value":{"entity-type":"item","numeric-id":5686093,"id":"Q5686093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$042041C3-F715-4B18-B24B-FFB4593208D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71d76f96dc35a01e600f993c6ab6ddc0f995bbbe","datavalue":{"value":{"entity-type":"item","numeric-id":2739443,"id":"Q2739443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$90D71284-9602-4035-9376-52C298688D64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b2a8dee9da43ea352edf4214339cba638abbd2d","datavalue":{"value":{"entity-type":"item","numeric-id":3548596,"id":"Q3548596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$FAE7764B-E465-4616-ACA8-5B00754CD310","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1743623c443c45d4efc4927d160fcf6689e1924","datavalue":{"value":{"entity-type":"item","numeric-id":1762665,"id":"Q1762665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$4652F00A-E8EE-4D84-A755-73FF9A6334BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f89b61d329ad779d609df68faf47cc84d5c6030d","datavalue":{"value":{"entity-type":"item","numeric-id":3433122,"id":"Q3433122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$17513459-83E3-429F-B203-BCDDEBE57E33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14dd3ac6843b1a40cf07c509793dce590c4e6527","datavalue":{"value":{"entity-type":"item","numeric-id":4011252,"id":"Q4011252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$C273C6BE-69FE-4B3C-88FA-7B8FF8FE5A45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b7d03acfe694d55b5bfb81a8721b654f11fafd6","datavalue":{"value":{"entity-type":"item","numeric-id":3139838,"id":"Q3139838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$A65B000C-DAB2-40A6-AD7C-0BB22251A342","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f215b4be5d109fd9d816f69f638d95cc094372e","datavalue":{"value":{"entity-type":"item","numeric-id":5552751,"id":"Q5552751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$E650C897-3E39-41DB-B5BB-3EFF01A1935F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e036a166ff302443b6807638b3ea2e4a2d93794e","datavalue":{"value":{"entity-type":"item","numeric-id":4379416,"id":"Q4379416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$E4E89405-FF6B-492C-97BF-5775310EDE20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2c242e76a337a687c37d0f3cbe491a531646399","datavalue":{"value":{"entity-type":"item","numeric-id":3158534,"id":"Q3158534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$EAC38540-2223-4244-919B-EC6AE8EDAE8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6ba9b60cd3c04771a309da0d2c2edf5029ef3e2","datavalue":{"value":{"entity-type":"item","numeric-id":4527265,"id":"Q4527265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$DF24F2ED-F27A-4DEB-9FF5-FB5A01AAC163","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4209d19a758993a85d84d4e4ead084f548231a18","datavalue":{"value":{"entity-type":"item","numeric-id":4039844,"id":"Q4039844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$63D58799-36C8-4CEB-94C6-5D205419C280","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$69FA28A9-EB93-4BF3-99F8-6C6DF365EBE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53f75e462884b81a2a160c58b8310283bf5ea06f","datavalue":{"value":{"entity-type":"item","numeric-id":677992,"id":"Q677992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$196E5DA3-8FD4-40D8-8C0E-CD31D8D9D583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6f882fe9dd4e77e007ce91fb979674cdc30b302","datavalue":{"value":{"entity-type":"item","numeric-id":4293510,"id":"Q4293510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$DBF7B9BE-14BB-458A-B2D6-51F5F0D4FE9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0dcf9fa5c74bacf2c63b3fd24cd264469e855b11","datavalue":{"value":{"entity-type":"item","numeric-id":2472733,"id":"Q2472733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$E5474943-7EC6-419C-9150-06D8B7331973","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67f4f9443ac15581ba5eb3baa9da42602bd9d881","datavalue":{"value":{"entity-type":"item","numeric-id":2555885,"id":"Q2555885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$FBD88495-CC61-4404-A060-EDFE794AE234","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef12561feaae1e5b152048326f8b405f2728a39f","datavalue":{"value":{"entity-type":"item","numeric-id":5190318,"id":"Q5190318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$CE8C648B-F053-4B21-88C2-0B8A3D80D80E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef282181b34aede598ef3d5726af5ef9efddfd13","datavalue":{"value":{"entity-type":"item","numeric-id":4660637,"id":"Q4660637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$CB08F255-AA72-4B93-A9E8-22C426299D1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f59373820f9472d4670b10101b8d86ff5312a229","datavalue":{"value":{"entity-type":"item","numeric-id":1767486,"id":"Q1767486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$5B2C1CD8-0D03-402D-B722-7ADC2F4A7AD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3952b9a9a384134e39f2740309369dfdbaec5fc","datavalue":{"value":{"entity-type":"item","numeric-id":3615934,"id":"Q3615934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$460D2591-A3F1-444D-8D1E-D2CB7737B159","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f41acd2273d80409c95755b579c825f32ee9b4f9","datavalue":{"value":{"entity-type":"item","numeric-id":4252163,"id":"Q4252163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$FCBF18C1-AF5D-4AB0-B15A-AF5DE94D0F63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2496d76f7d7fec9d96f39f6e3a59ed93c78d8e95","datavalue":{"value":{"entity-type":"item","numeric-id":1165896,"id":"Q1165896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$BC1920AD-F4A3-4684-ACA1-EAD441AF6902","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1413924d331e6cd5ce831e9b213a571314d89a59","datavalue":{"value":{"entity-type":"item","numeric-id":2650275,"id":"Q2650275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$C33149AA-D2BB-422A-B1B0-A69BFB9D4D32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fdbe2f4b1b17f872e7dca2dfd26bb9e0b0cf97c0","datavalue":{"value":{"entity-type":"item","numeric-id":1578508,"id":"Q1578508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$F8A70C95-6D86-4959-8861-848FA403ACDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3339b24cef8836eac890e3591c6339f410552669","datavalue":{"value":{"entity-type":"item","numeric-id":1587233,"id":"Q1587233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$E1B84984-DA6F-4998-9B7A-5CF42C5C9585","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"878cae14e4bc5f39d4b25393ae13db2b58da6aa1","datavalue":{"value":{"entity-type":"item","numeric-id":4424888,"id":"Q4424888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$2E5F1951-E812-4622-B89F-C0D9E627A96A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6462e8c5c0aea01f2a594c3439645ce7174b0eb2","datavalue":{"value":{"entity-type":"item","numeric-id":4947407,"id":"Q4947407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$AD739A68-ADC8-439A-AFD4-4BCBEEAD4501","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$B777EE11-3FD6-4AEA-B5AB-EEFF454F2D23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bbaa88fa4bc73a806971af91313862449fcfadd","datavalue":{"value":{"entity-type":"item","numeric-id":1062447,"id":"Q1062447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$D587C94F-F375-4B65-9DD2-006060214DF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"296c71adbea8a21622a38015e5a468a15c610de7","datavalue":{"value":{"entity-type":"item","numeric-id":1826301,"id":"Q1826301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$CB26B395-CAC0-4579-AD3D-0981679D75BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da454e950fde321eae2015612f725dcc6ec349dc","datavalue":{"value":{"entity-type":"item","numeric-id":5308231,"id":"Q5308231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$F7FF5139-2C0F-4E9D-9260-9704A62324D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37b021cc6d4f4e531cba540b45ffe7869eddc1d7","datavalue":{"value":{"entity-type":"item","numeric-id":4027997,"id":"Q4027997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$0B59AC51-CB99-4770-8785-9EEFA26766A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09e0eea87a946bd4a9e36504ce8daaedf2ef4f1e","datavalue":{"value":{"entity-type":"item","numeric-id":4492826,"id":"Q4492826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$14363F7A-F8A5-47C1-B4C6-7C2D68297AF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ff82bf0f41d95d6f162b7142f7d2587480b327","datavalue":{"value":{"entity-type":"item","numeric-id":4737511,"id":"Q4737511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$1FE1376A-DFB0-40DC-901C-ADCF461151B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45693627939fec63d2836fa11bb5f307d8dbed5a","datavalue":{"value":{"entity-type":"item","numeric-id":3899517,"id":"Q3899517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$7130866F-E167-4665-960A-29314DAB5351","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9da36db8ec75b91821c4a63578e47a9063391f93","datavalue":{"value":{"entity-type":"item","numeric-id":5670687,"id":"Q5670687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$7BF867A8-BFC1-4A32-B768-E39131FF0852","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87660c9c5fdc45e0d7335aa6496613f4289eb45a","datavalue":{"value":{"entity-type":"item","numeric-id":4391214,"id":"Q4391214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$C6F3A4E3-6ADC-4240-A0B5-3DEA76953E04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bf1fd8fdee548d2fca2445a7bd3bbfaab617c4f","datavalue":{"value":{"entity-type":"item","numeric-id":5343475,"id":"Q5343475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$99C83BA9-FD1D-44F5-9ECB-030F92256525","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba574a3fa69782816566925d59607182b871e147","datavalue":{"value":{"entity-type":"item","numeric-id":4193559,"id":"Q4193559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$76620A74-AB05-4375-A5C5-C6F743AD7CAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be27ac4d38efd36cab2099f47e12db1c6aeb62aa","datavalue":{"value":{"entity-type":"item","numeric-id":5790661,"id":"Q5790661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$5F3503E7-F072-485C-B814-223404A39A04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0470c0aaac81d931e42aa4c241636749452afef2","datavalue":{"value":{"entity-type":"item","numeric-id":4296321,"id":"Q4296321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$8DE8A25C-BA86-4541-802D-941715B08913","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b9d413a4029e3f167aa73f48f47356d2f38087d7","datavalue":{"value":"10.1016/J.JSC.2011.09.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412210$4374539F-B6E9-4C13-9075-C3A318919463","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"433ef5afde58e713e0c45e65a025972b93f95bf2","datavalue":{"value":{"entity-type":"item","numeric-id":250768,"id":"Q250768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$6CD8E225-B3BB-467A-BC6E-4759A2B923EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cb7c70e512672c14c3beda31995db16425d537dd","datavalue":{"value":{"entity-type":"item","numeric-id":857527,"id":"Q857527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$9A027A3E-DA8C-4B1B-A445-139AD4A86F0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bc5509e998274f69b00a242d8ae4aa321beae036","datavalue":{"value":{"entity-type":"item","numeric-id":202083,"id":"Q202083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$28512655-3EE9-416D-AA04-907B4A18F6A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d27ffa0093deda83d064c510b3c6ece126b50b50","datavalue":{"value":{"entity-type":"item","numeric-id":3105517,"id":"Q3105517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412210$4CF24343-39EE-4EFE-B88A-A686A5B1838B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e7509db932701ba6470067e07cfb1c48b7d9e8a2","datavalue":{"value":"For an input Laurent polynomial system \\(F \\in \\bigcup_{k,n \\in \\mathbb{N}}( \\mathbb{Z}[x_1^{\\pm 1},\\dots,x_n^{\\pm 1}])^k\\), let \\(\\text{FEAS}_{\\mathbb{Q}_{\\text{primes}}}\\) denote the problem of deciding whether \\(F\\) has a \\(p\\)-adic rational root. If \\(f(x) := \\sum_{j=1}^m c_jx^{a_j}\\), with \\(c_j \\in \\mathbb{R}\\setminus \\{0\\}\\) for all \\(j\\), and \\(x^{a_j} = x_1^{a_{1j}}\\cdots x_n^{a_{nj}}\\), then size(\\(f\\)) := \\(\\sum_{i=1}^m \\log_2[(2+|c_i|)(2+|a_{1j}|) \\cdots (2+|a_{nj}|)\\). When the prime \\(p\\) is fixed, the input size will be size(\\(f\\)), but when the prime \\(p\\) is allowed to range over all or a subfamily of primes, the input size will be \\(\\text{size}(f)+\\log(p)\\). Size\\((F)\\) is the sum of the sizes of the polynomials defining \\(F\\). If the \\(a_j\\) are pairwise distinct, \\(f\\) is an \\textit{\\(n\\)-variate \\(m\\)-nomial}. If, additionally, the volume of the Newton polytope of \\(f\\) is positive, \\(f\\) is said to be an \\textit{honest \\(n\\)-variate \\(m\\)-nomial}. Only honest \\(n\\)-variate \\(m\\)-nomials are considered in the paper. NEWLINENEWLINENEWLINE NEWLINEGiven the above definitions, the authors prove that the detection of \\(p\\)-adic rational roots is: NEWLINE{\\parindent=7mmNEWLINE\\begin{itemize}\\item[{\\(*\\)}]\\textbf{NP}-complete for honest \\(n\\)-variate (\\(n+1\\))-nomials,NEWLINE\\item[{\\(*\\)}]of constant-time complexity for certain special families of \\(n\\)-variate (\\(n+1\\))-nomials when \\(p\\) exceeds the Newton polytope volume NEWLINE\\item[{\\(*\\)}]\\textbf{NP} for trinomials in one variable NEWLINE\\item[{\\(*\\)}]\\textbf{NP}-hard for sparse polynomials in one variable with respect to randomized reductions. NEWLINENEWLINENEWLINE\\end{itemize}} NEWLINEAdditionally, the authors prove that, for \\(f \\in \\mathbb{Z}[x_1]\\), if there were randomized algorithms of expected complexity polynomial in \\(\\text{size}(f)+\\log(p)\\) for factoring \\(f\\) over \\(\\mathbb{Q}_p[x_1]\\), then \\textbf{NP} \\(\\subseteq\\) \\textbf{ZPP}.NEWLINENEWLINEThe univariate \\textbf{NP}-hardness proof requires the efficient construction of primes in certain arithmetic progressions, which the authors also prove possible.","type":"string"},"datatype":"string"},"type":"statement","id":"Q412210$2F47B342-2014-4C1D-AFC7-52085CD2159C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69aeb82694c782291186910c37fefd67258188c8","datavalue":{"value":{"entity-type":"item","numeric-id":2946560,"id":"Q2946560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"264eea9f2e47acff900a11f51f4c073ce32b833a","datavalue":{"value":{"amount":"+0.8970431685447693","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":"Q412210$53057141-7E6F-46A6-9DAA-A8D00D9CE1F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"412b69b3004fff6cc8e1d5310c5be66ab4fe190e","datavalue":{"value":{"entity-type":"item","numeric-id":2167518,"id":"Q2167518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc5f11057d8b2bafaa9f017943fe13f61ccade01","datavalue":{"value":{"amount":"+0.8216970562934875","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":"Q412210$4BCC2068-9C88-4432-B428-F7EB78E2F2B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c0339bf9761929ce4429096dfe9c6515aa66c09","datavalue":{"value":{"entity-type":"item","numeric-id":2883798,"id":"Q2883798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e5b258459cdb1298d75ace97a6f361a34f242dd","datavalue":{"value":{"amount":"+0.814475953578949","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":"Q412210$0E7CCE13-3835-434E-8D67-F689443551A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3234061d926557b9f1baca9f049532c02701c240","datavalue":{"value":{"entity-type":"item","numeric-id":2963217,"id":"Q2963217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"990aa19dbe9613ee3de5bf918c7b224011ad5c86","datavalue":{"value":{"amount":"+0.8039811849594116","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":"Q412210$78803A47-EC5B-4860-AFF3-4F8E88D451AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8560aeb2905451ada1371bf6e6070f6b11d51aa2","datavalue":{"value":{"entity-type":"item","numeric-id":2816831,"id":"Q2816831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0fec9b9d9b82f63f25fa28feb90d0a090e7bfb4","datavalue":{"value":{"amount":"+0.7999112606048584","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":"Q412210$91D4FC23-5274-47A4-8331-91AAFC95D497","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Faster \\(p\\)-adic feasibility for certain multivariate sparse polynomials","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Faster_%5C(p%5C)-adic_feasibility_for_certain_multivariate_sparse_polynomials"}}}}}