{"entities":{"Q4375789":{"pageid":6405388,"ns":120,"title":"Item:Q4375789","lastrevid":108320507,"modified":"2026-11-05T22:02:04Z","type":"item","id":"Q4375789","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1114020"}},"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":"Q4375789$0EDD672F-28C4-474E-92AD-FC67B36D8055","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5365725d758a397b677c5c8d624b1a05fd7dbc6f","datavalue":{"value":"0897.03029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4375789$850E58DF-AAE5-4803-A950-22FCAFBC036B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"057c48278a1d014d58f7703e66b1dc164eccfbc4","datavalue":{"value":{"entity-type":"item","numeric-id":175527,"id":"Q175527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4375789$027B84BD-C2CA-441C-A9E5-881F4DCCA153","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2356fe1f1f6d7960e11f0114cbd6aa7fe05024f7","datavalue":{"value":{"entity-type":"item","numeric-id":247180,"id":"Q247180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4375789$47B02A6A-CB2E-471C-A4EB-462A00AE4755","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dbb41ef53af0bcae962dabb6b64860c4703506e5","datavalue":{"value":{"entity-type":"item","numeric-id":845873,"id":"Q845873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4375789$A5D96691-C11C-4D30-9E3D-12154319CDE5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e8212d9707fd326a29dd942aeda2a7be1e26dc9d","datavalue":{"value":{"time":"+1998-10-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4375789$B0776627-6BD4-4D7A-B391-E094EF83A4D0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b58df756e27df0e7b4d6d54dbbfd9015b563e63d","datavalue":{"value":"03C13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4375789$E38DC73C-DB22-4DAD-B4BD-52F59FD92147","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4375789$76CD6650-7833-4578-B4D9-44F6360FDF85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4375789$ACA9A891-8A1D-49B0-8B3D-BB6DF8CAA298","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6ee9f5484d11a01fb95552e5bea2154ebac0877","datavalue":{"value":"03D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4375789$F3A9607B-D12C-437B-BD40-5FD443DBC8AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4375789$0FF11EC5-C5EC-4095-B591-31E25A4C3AD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"758b4d196a1f97708f26591fee42c00739e26cc0","datavalue":{"value":"03D80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4375789$1A474A57-892F-4BA6-B688-20291203FDE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4375789$C0F7A915-746B-4B0D-AB79-273080DB92D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4375789$5663751A-05A9-4B49-9735-7512217688A7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"03181f735345d4602092be40c4f7ee077e2aafdb","datavalue":{"value":"1114020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4375789$36F57A0E-4EFE-4351-8153-AC40D9A005D6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"285cbda6a32740408844615a92ae883f49144d06","datavalue":{"value":"parametrized problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q4375789$56370FEF-422A-4580-9183-E7B0E4734E05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1520de8379415749656b1e95045c660d5b7f1330","datavalue":{"value":"fixed-parameter tractability","type":"string"},"datatype":"string"},"type":"statement","id":"Q4375789$1BF7D14D-4237-4ED1-A8BA-9413D58AD4AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ecf85431442bdec9ecc8b56948e78a907f17e7b","datavalue":{"value":"\\(W\\) hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q4375789$8F19B7DD-F0A7-4F3B-8984-81EB9FAE14A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0421a88d9599388a9af4b0e2102ab403f6c36e7f","datavalue":{"value":"finite model theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q4375789$9C739C26-1C01-42C4-9945-51153078C383","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee63604621b6fd9d90b10f19ccdd9c167a66b1b6","datavalue":{"value":"parameterized complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4375789$E7ED5FC0-552C-4521-80F9-081DC3D2BC27","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":"Q4375789$FF3FB090-AFF1-47EE-82C8-D22559ED12F4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e86a5b7440186ac57df521dbb97d281323c32d63","datavalue":{"value":{"entity-type":"item","numeric-id":4281497,"id":"Q4281497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57896341aeb7d3e6e9c2366a7364dc2979dd1842","datavalue":{"value":{"amount":"+0.8450005054473877","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":"Q4375789$1DA2678F-2B08-4621-AF11-07A90027DFDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"156ebe50db5ab0b43aa7bc4e74bb563ec47b5c40","datavalue":{"value":{"entity-type":"item","numeric-id":3182930,"id":"Q3182930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52c588273188135fdda1a5ed6cb83d19ff73586b","datavalue":{"value":{"amount":"+0.8420277237892151","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":"Q4375789$0CA592E2-69DB-4B8D-A18F-FBBDEB2B02B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f468d8ab7b55a529f822425871d1e73220f811d","datavalue":{"value":{"entity-type":"item","numeric-id":2719133,"id":"Q2719133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"792483622115860bffb44b08bc42244375f9ce59","datavalue":{"value":{"amount":"+0.8313407897949219","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":"Q4375789$2652B59C-B58A-4CCD-A259-027EB3F9833F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1cad4d2c16945804b6d68f30f8c4ef9205136552","datavalue":{"value":"A parameterized language is a set of pairs of a binary string \\(x\\) and a natural number \\(k\\). Examples for parameterized languages are given by the set \\(P_0\\) of all pairs \\((x,k)\\) where \\(x\\) is (an appropriate code of) a graph which has a vertex cover of size \\(k\\), and by the set \\(P_1\\) of all pairs \\((x,k)\\) where \\(x\\) is a graph which has a clique of size \\(k\\). A parameterized language \\(L\\) belongs to the class FPT of fixed-parameter tractable languages iff there is a polynomial \\(p\\), a function \\(f\\) from the naturals to the naturals, and a Turing machine \\(M\\), where \\(M\\) decides on input \\((x,k)\\) in time \\(f(k) \\cdot p (| x|)\\) whether \\(x\\) is in \\(L\\). \\textit{R. G. Downey} and \\textit{M. R. Fellows} introduced in a previous paper [SIAM J. Comput. 24, 873-921 (1995; Zbl 0830.68063)] a reducibility \\(\\leq_m^{\\text{fpt}}\\) between parameterized problems, as well as a hierarchy \\(\\text{FPT}\\subseteq W[1]\\subseteq W[2] \\subseteq \\ldots\\). of classes of parameterized languages. All these classes are closed downwards under \\(\\leq_m^{\\text{fpt}}\\), and consequently, unless the hierarchy collapses to one of its levels, a parameterized language which is \\(\\leq_m^{\\text{fpt}}\\)-hard for \\(W[t]\\) cannot be contained in FPT or in \\(W[j]\\) for \\(j<t\\). Hence the relative complexity of parameterized languages can be compared via relating them to the \\(W\\) hierarchy. For example \\(P_1\\) might be viewed as being more complex than \\(P_0\\), because \\(P_0\\) is in FPT, while \\(P_1\\) is \\(\\leq_m^{\\text{fpt}}\\)-complete for \\(W[1]\\). For background on parameterized complexity see \\textit{R. G. Downey} and \\textit{M. R. Fellows}'s forthcoming textbook: Parameterized complexity (1998). As their main result, the authors show that for each \\(t \\geq 1\\), the class \\(W[t]\\) is equal to the downward closure under \\(\\leq_m^{\\text{fpt}}\\) of the class of languages definable by formulae of the form \\(\\phi=(\\exists U)\\psi\\) where \\(U\\) is a set variable and \\(\\psi\\) is a first-order formula in prenex form with a leading \\(\\forall\\)-quantifier and at most \\(t-1\\) quantifier alternations. Here a specific logic is considered where the intended models are binary strings, and a language \\(L\\) is definable by a formula \\(\\phi\\) iff \\(L\\) contains exactly the strings which satisfy \\(\\phi\\). For details see the references cited in the text and for background see \\textit{H.-D. Ebbinghaus} and \\textit{J. Flum}'s textbook: Finite model theory (1995; Zbl 0841.03014). In addition, the authors give an equivalent form of their characterization in terms of sequences of first-order formulae of some special form which depends on \\(t\\). Here, for a language \\(L\\) in \\(W[t]\\) the \\(k\\)th formula in the sequence defines the slice \\(P_k := \\{x : (x,k) \\in L \\}\\) of \\(L\\). Finally, the characterization of the classes \\(W[t]\\) are applied for classifying some parameterized languages in the \\(W\\) hierarchy. As noted by the authors, the characterization of the classes \\(W[t]\\) in terms of second-order logic over finite strings resembles Fagin's and Stockmeyer's characterizations of the class NP and the polynomial time hierarchy, respectively [see \\textit{R. Fagin}, Complexity of Comput., Proc. Symp. Appl. Math., New York City 1973, 43-73 (1974; Zbl 0303.68035), and \\textit{L. Stockmeyer}, Theor. Comput. Sci. 3, 1-22 (1977; Zbl 0353.02024)], as well as subsequent results on NP optimization problems obtained by \\textit{C. Papadimitriou} and \\textit{M. Yannakakis} [J. Comput. Syst. Sci. 43, No. 3, 425-440 (1991; Zbl 0765.68036)]. For the entire collection see [Zbl 0881.00033].","type":"string"},"datatype":"string"},"type":"statement","id":"Q4375789$ADB1D7E4-2DA5-4380-84C1-756018F7F118","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4375789","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4375789"}}}}}