{"entities":{"Q1978701":{"pageid":1989443,"ns":120,"title":"Item:Q1978701","lastrevid":47007036,"modified":"2025-12-26T01:10:07Z","type":"item","id":"Q1978701","labels":{"en":{"language":"en","value":"Cook's versus Valiant's hypothesis"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1454435"}},"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":"Q1978701$BACE853E-01DD-443C-A359-FDACA092236A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9db6a03aa87b2e84c9f5fac91ca75963d227ed56","datavalue":{"value":{"text":"Cook's versus Valiant's hypothesis","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1978701$801180F4-D90C-4409-9463-8695A6AFFF0C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"581b21edb160370ebcfd053717835d4cf0db2912","datavalue":{"value":"0943.68070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1978701$07AB4A9F-28C5-4EC8-88A8-7DAB43B0E750","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5786967456d7bb978e2bfec2838d126fe0eb0fb2","datavalue":{"value":"10.1016/S0304-3975(99)00183-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1978701$7C44406A-56A7-4FD1-887B-3042903D0D0A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e924ed081f4605dc26607b8aca3d4232bbd94111","datavalue":{"value":{"entity-type":"item","numeric-id":254894,"id":"Q254894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$8A9198C3-E545-4FE6-BB04-DA65DA77E5BF","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":"Q1978701$14D4A438-AFD9-42EC-91DF-70C43F34AE29","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cea4e04940bd3504f3c0f2b605e025bc106fb722","datavalue":{"value":{"time":"+2000-06-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":"Q1978701$E9097509-1132-498E-A0B6-241C9B51E791","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ceff01a3e8e1ab199a438cd7c545b6b355088733","datavalue":{"value":"Valiant developed a nonuniform algebraic analogue of the theory of NP-completeness for computations with polynomials over a field \\(k\\) in [\\textit{L. G. Valiant}, Proceedings of the 11th ACM STOC, 1979, pp. 249-261; Logic and algorithmic, int. Symp., Z\u00fcrich 1980, Monogr. L'Enseign. Math. 30, 365-380 (1982; Zbl 0474.68062)]. This theory centers around his hypothesis VP\\(_{k}\\neq\\)VNP\\(_{k}\\), the analogue of Cook's hypothesis P\\(\\neq\\)NP. We identify the Boolean parts of Valiant's algebraic complexity classes VP\\(_{k}\\) and VNP\\(_{k}\\) as familiar nonuniform complexity classes. As a consequence, we obtain rather strong evidence for Valiant's hypothesis: if it were wrong, then the nonuniform versions of NC and PH would be equal. In particular, the polynomial hierarchy would collapse to the second level. We show this for fields of characteristic zero and finite fields; in the first case we assume a generalized Riemann hypothesis. The crucial step in our proof is the elimination of constants in \\(k\\), which relies on a recent method proposed by \\textit{P. Koiran} [J. Complexity 12, No. 4, 273-286, Art. No. 0019 (1996; Zbl 0862.68053)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978701$CD41FF07-19BE-4794-8592-455720456B0F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1978701$C7CEEA4C-D18F-4F27-8666-DDEE9E2F3CEF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f3a55d52ebfdde5eb901bb0a68d1b54b6d6dc7ac","datavalue":{"value":"1454435","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1978701$BB4F9335-E280-4335-87E9-86A11950589E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"010c7d2ed2de24e1d8a535188cc19c40627ba1be","datavalue":{"value":"algebraic complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978701$0FAA8C0A-4057-43A3-9A7A-65F05C3EEC42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978701$A23B6AA9-17FD-4347-813A-FDE69A5D14C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8acc88f749584274e30276f81e49467cdeb17278","datavalue":{"value":"elimination of constants","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978701$F99132D3-454D-4BB3-887D-4EB94E79C1EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67e0c662da641b0bde8d9859582e6bb9a7473eeb","datavalue":{"value":"reduction modulo primes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978701$CFFB9494-C499-455B-A137-D1A405B108DB","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":"Q1978701$46CDB3CB-ADFA-44A7-A837-406FEF5D946E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"233b0d1b99b8001d6aea8c4b2bab778ddad6115e","datavalue":{"value":{"entity-type":"item","numeric-id":685721,"id":"Q685721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$6170954C-9846-4F05-BF0D-CF08CC47CBCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5324e8e57b25ca183b0d851ce507af9e5f39d284","datavalue":{"value":{"entity-type":"item","numeric-id":4717931,"id":"Q4717931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$DDDB9F83-48F6-416B-B7B3-6448D26EFF37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1efc6d224ffe0d7322355df220a9a0a92863a911","datavalue":{"value":{"entity-type":"item","numeric-id":4729768,"id":"Q4729768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$9CB4387A-8F5E-4102-AD16-C66A99872F8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5ecdd6ae796ed37ec9a32b57a9664c1168692f3","datavalue":{"value":{"entity-type":"item","numeric-id":1567446,"id":"Q1567446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$1479D6EB-7D61-41EA-8AFA-96D4D637F3DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6831af1b72f53f70fcbca0828235127a91c4aeb2","datavalue":{"value":{"entity-type":"item","numeric-id":3836529,"id":"Q3836529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$AB228E4D-753E-4C28-BB6D-6A40E1A021FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a6077e2e54fd6a54fd3728489a248cfff870e3c","datavalue":{"value":{"entity-type":"item","numeric-id":4331740,"id":"Q4331740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$0C531ED1-CFFA-4B77-92EA-8EC7F2098BD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b7948d2ae997be513a92df2486b836c4e1eaa12","datavalue":{"value":{"entity-type":"item","numeric-id":5667480,"id":"Q5667480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$405A96B7-4F8F-466C-9D08-898FF92D913F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62eddfdb4e01273bd747531464c286640dafcddd","datavalue":{"value":{"entity-type":"item","numeric-id":4337443,"id":"Q4337443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$6BD8567B-50EA-4FB9-BC80-E1A7F4BAF629","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f36f5bcaab67710a0bd4aa3b08dcd847fbeb364","datavalue":{"value":{"entity-type":"item","numeric-id":1114391,"id":"Q1114391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$34B3598A-A2C1-4F9E-AD70-F4EC7F60FCA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86a33fe97dc70377c6d17a704f13f0cbe608566b","datavalue":{"value":{"entity-type":"item","numeric-id":4850731,"id":"Q4850731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$D4A096A2-36C4-4EAF-BB68-A8E02097032F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c568fbb12fc5452c9699a0a3e0159154b2a6454a","datavalue":{"value":{"entity-type":"item","numeric-id":4385525,"id":"Q4385525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$8BC6C2B3-8F28-494E-A3CA-BC88F8C58092","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df9b440a7e27b4753042460b886584e943bebd26","datavalue":{"value":{"entity-type":"item","numeric-id":3957950,"id":"Q3957950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$6B20B04D-12F5-452D-81AF-1F96BBE90A7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84bbca1bd52a8b705768d2a03b4b5b5c1b7c0d27","datavalue":{"value":{"entity-type":"item","numeric-id":4385522,"id":"Q4385522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$D6C7401D-84AA-40C9-A855-FEBE0DADCD1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca5a9784d90b4a01fac7273c96c2804a2c9ca767","datavalue":{"value":{"entity-type":"item","numeric-id":2365408,"id":"Q2365408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$17D6657D-8F95-4DBF-9478-74CFDE56636C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85613e4bb008e11f1a85666a8b80134711e202a8","datavalue":{"value":{"entity-type":"item","numeric-id":4297380,"id":"Q4297380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$A0E93B42-AF02-4066-B741-96A65BF78156","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1eae5b6f02f8ae28a77f47071ab9453c53a0feef","datavalue":{"value":{"entity-type":"item","numeric-id":4714022,"id":"Q4714022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$D0004F1C-6A2C-40FD-897D-9D532CB1E1A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"def75084efbc0fbf44ea077c778b5e03e6bb2f5e","datavalue":{"value":{"entity-type":"item","numeric-id":4135671,"id":"Q4135671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$E85B41AB-A64D-41C2-A024-E84DDF8DE4CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7210dd0063c20bab70607fcfa8991587a187e7af","datavalue":{"value":{"entity-type":"item","numeric-id":5906056,"id":"Q5906056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$B6264828-04D0-4870-80EC-A0348B81EFF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40091ccc3aff16816fcd9d4de3cdee129acc7541","datavalue":{"value":{"entity-type":"item","numeric-id":3963114,"id":"Q3963114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$76D3ED50-BBFA-4440-9782-1C0A7A9007D1","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":"Q1978701$3F1B9056-6D05-46D0-B976-0E1401AE228C","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":"Q1978701$E9C530CF-7EF8-4EC4-B93B-B5DB6143FD9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf5dbca3bca818ebbb87eec6505d6d3a400d5ab1","datavalue":{"value":{"entity-type":"item","numeric-id":3929052,"id":"Q3929052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$8CD6A07E-B86F-4065-B75D-2A7AF3227995","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da1e2a210a633c08ab99ee4d2a519f4798177e87","datavalue":{"value":{"entity-type":"item","numeric-id":3036703,"id":"Q3036703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$47E95ED1-6C19-44E6-A5E7-5D8E025E4C74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1dfd82bed9266a9eb9ee03c49c86a8c45cb2436","datavalue":{"value":{"entity-type":"item","numeric-id":1090454,"id":"Q1090454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$FE71606E-F671-4A9E-9C46-CF92B66D9BBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35907d675520ff12d0c71a74a5a1ec1a28b4f7d6","datavalue":{"value":{"entity-type":"item","numeric-id":4773795,"id":"Q4773795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$4D67CB1A-1EE3-4F4B-8EAB-1DD2AD001327","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8879dfa57e403b893d92ba625acbba97aed20922","datavalue":{"value":{"entity-type":"item","numeric-id":3329545,"id":"Q3329545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978701$1669743E-2B48-4471-9127-944FFDF8A7BC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8601638d761691bc684aaf5a53faa69c25af481","datavalue":{"value":{"entity-type":"item","numeric-id":4381389,"id":"Q4381389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"566f54cd2a3da7570174e7091051f974d95e1509","datavalue":{"value":{"amount":"+0.853044331073761","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":"Q1978701$DD40B2AF-4CBF-4D5B-B3B4-00B71E4ACEAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5782270d178db62a11c34dc6982ebdd7c0b02ce","datavalue":{"value":{"entity-type":"item","numeric-id":3836529,"id":"Q3836529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac93b6769c516517713fdcee88f698af81a40388","datavalue":{"value":{"amount":"+0.8522489070892334","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":"Q1978701$A3AB9C3C-AA0F-4E7A-A0D9-A233DCBD1E4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9388409b38ce5e42b3cead34ee710e78d38a5339","datavalue":{"value":{"entity-type":"item","numeric-id":1567446,"id":"Q1567446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d813b299b776103c140f864c874cebc45c2cc865","datavalue":{"value":{"amount":"+0.8328176736831665","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":"Q1978701$16DF798C-B7E6-4097-ADF8-2F456C8980C7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1978701","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1978701"}}}}}