{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:43:47Z","timestamp":1787341427740,"version":"build-2736575974"},"reference-count":51,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100004895","name":"European Social Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004895","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>The hypergraph duality problem Dual is defined as follows: given two simple hypergraphs $\\mathcal{G}$ and $\\mathcal{H}$, decide whether $\\mathcal{H}$ consists precisely of all minimal transversals of $\\mathcal{G}$ (in which case we say that $\\mathcal{G}$ is the dual of $\\mathcal{H}$ or, equivalently, the transversal hypergraph of $\\mathcal{H}$). This problem is equivalent to deciding whether two given nonredundant monotone disjunctive normal forms\/conjunctive normal forms are dual. It is known that $\\overline{{\\sc Dual}}$, the complementary problem to Dual, is in GC($\\log^2 n$, PTIME), where GC($f(n)$, $\\mathcal{C}$) denotes the complexity class of all problems that after a nondeterministic guess of $O(f(n))$ bits can be decided (checked) within complexity class $\\mathcal{C}$. It was conjectured that $\\overline{{\\sc Dual}}$ is in GC($\\log^2 n$, LOGSPACE). In this paper we prove this conjecture and actually place the $\\overline{{\\sc Dual}}$ problem into the complexity class GC($\\log^2 n$, TC$^{0}$) which is a subclass of GC($\\log^2 n$, LOGSPACE). We here refer to the logtime-uniform version of TC$^{0}$, which corresponds to FO(COUNT), i.e., first order logic augmented by counting quantifiers. We achieve the latter bound in two steps. First, based on existing problem decomposition methods, we develop a new nondeterministic algorithm for $\\overline{{\\sc Dual}}$ that requires one to guess $O(\\log^2 n)$ bits. We then proceed by a logical analysis of this algorithm, allowing us to formulate its deterministic part in FO(COUNT). From this result, by the well-known inclusion ${TC$^0$}\\subseteq{LOGSPACE}$, it follows that Dual also belongs to ${DSPACE}[\\log^2 n]$. Finally, by exploiting the principles on which the proposed nondeterministic algorithm is based, we devise a deterministic algorithm that, given two hypergraphs $\\mathcal{G}$ and $\\mathcal{H}$, computes in quadratic logspace a transversal of $\\mathcal{G}$ missing in $\\mathcal{H}$.<\/jats:p>","DOI":"10.1137\/15m1027267","type":"journal-article","created":{"date-parts":[[2018,4,12]],"date-time":"2018-04-12T13:20:03Z","timestamp":1523539203000},"page":"456-492","source":"Crossref","is-referenced-by-count":7,"title":["Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic"],"prefix":"10.1137","volume":"47","author":[{"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Enrico","family":"Malizia","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,4,12]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90022-D"},{"key":"atypb2","unstructured":"C. Berge,\n                      Hypergraphs\n                      , Vol. 45 of North-Holland Math. Libr., North-Holland, Amsterdam, 1989."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1157"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"E. Boros, V. Gurvich, L. Khachiyan, and K. Makino,\n                      On the complexity of generating maximal frequent and minimal infrequent sets\n                      , in Proceedings of the STACS 2002 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes - Juan les Pins, France, 2002, Lecture Notes in Comput. Sci. 2285 H. Alt and A. Ferreira, eds., Springer, Berlin, 2002, pp. 133-141,https:\/\/doi.org\/10.1007\/3-540-45841-7_10.","DOI":"10.1007\/3-540-45841-7_10"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1023\/A:1024605820527"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"E. Boros and K. Makino,\n                      A fast and simple parallel algorithm for the monotone duality problem\n                      , in Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP 2009, Part I, Rhodes, Greece, 2009, Lecture Notes in Comput. Sci. 5555, S. Albers, A. Marchetti-Spaccamela, Y. Matias, S. Nikoletseas, and W. Thomas, eds., Springer, Berlin, 2009, pp. 183-194,https:\/\/doi.org\/10.1007\/978-3-642-02927-1_17.","DOI":"10.1007\/978-3-642-02927-1_17"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793258295"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"S. Cook and P. Nguyen,\n                      Logical foundations of proof complexity\n                      , Cambridge University Press, Cambridge, UK, 2010.","DOI":"10.1017\/CBO9780511676277"},{"key":"atypb9","unstructured":"H.D. Ebbinghaus and J. Flum,\n                      Finite Model Theory\n                      , Springer Monogr. Math., 2nd ed., Springer, Berlin, 1999."},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"H.D. Ebbinghaus, J. Flum, and W. Thomas,\n                      Mathematical Logic\n                      , Undergrad. Texts Math., 2nd ed., Springer, New York, 1994.","DOI":"10.1007\/978-1-4757-2355-7"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250299"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"T. Eiter and G. Gottlob,\n                      Hypergraph transversal computation and related problems in Logic and AI\n                      , in Proceedings of European Conference on Logics in Artificial Intelligence, JELIA 2002, Cosenza, Italy, S. Flesca, S. Greco, N. Leone, and G. Ianni, eds., Lecture Notes in Comput. Sci. 2424, Springer, Berlin, 2002, pp. 549-564,https:\/\/doi.org\/10.1007\/3-540-45757-7_53.","DOI":"10.1007\/3-540-45757-7_53"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970240639X"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"T. Eiter and K. Makino,\n                      Generating all abductive explanations for queries on propositional Horn theories\n                      , in Proceedings of the 17th International Workshop on Computer Science Logic, CSL 2003, Proceedings of the 12th Annual Conference of the EACSL, 8th Kurt G\u00f6del Colloquium, KGC 2003, Vienna, Austria, 2003, M. Baaz and J. A. Makowsky, eds., Lecture Notes in Comput. Sci. 2803, Springer, Berlin, 2003, pp. 197-211,https:\/\/doi.org\/10.1007\/978-3-540-45220-1_18.","DOI":"10.1007\/978-3-540-45220-1_18"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.04.017"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.05.030"},{"key":"atypb17","unstructured":"J. Flum and M. Grohe,\n                      Parameterized Complexity Theory\n                      , Texts Theoret. Comput. Sci. EATES Ser., Springer, Berlin, 2006."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.06.003"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0062"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4223"},{"key":"atypb21","unstructured":"D. R. Gaur,\n                      Satisfiability and Self-Duality of Monotone Boolean Functions\n                      , Ph.D. thesis, School of Computing Science, Simon Fraser University, Burnaby, Canada, 1999."},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"D. R. Gaur and R. Krishnamurti,\n                      Average case self-duality of monotone Boolean functions\n                      , in Advances in Artificial Intelligence. 17th Conference of the Canadian Society for Computational Studies of Intelligence, Canadian AI 2004, London, Canada, 2004, Proceedings, A. Y. Tawfik and S. D. Goodwin, eds., Lecture Notes in Comput. Sci. 3060, Springer, Berlin, 2004, pp. 322-338,https:\/\/doi.org\/10.1007\/978-3-540-24840-8_23.","DOI":"10.1007\/978-3-540-24840-8_23"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1613\/jair.380"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1145\/235767.235769"},{"key":"atypb25","first-page":"25","author":"Gottlob G.","year":"2013","journal-title":"New York"},{"key":"atypb26","first-page":"385","volume":"9","author":"Gottlob G.","year":"1990","journal-title":"Acta Cybernet."},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"G. Gottlob and E. Malizia,\n                      Achieving new upper bounds for the hypergraph duality problem through logic\n                      , in Proceedings of the Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic (CSL) and the 29th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS) (CSL-LICS 2014), T. A. Henzinger and D. Miller, eds., ACM, New York, 2014,https:\/\/doi.org\/10.1145\/2603088.2603103.","DOI":"10.1145\/2603088.2603103"},{"key":"atypb28","unstructured":"G. Gottlob and E. Malizia,\n                      Achieving New Upper Bounds for the Hypergraph Duality Problem Through Logic\n                      , 2017,https:\/\/arxiv.org\/abs\/1407.2912."},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(89)90079-9"},{"key":"atypb30","first-page":"209","author":"Gunopulos D.","year":"1997","journal-title":"New York"},{"key":"atypb31","unstructured":"M. Hagen,\n                      Algorithmic and Computational Complexity Issues of MONET\n                      , Cuvillier, G\u00f6ttingen, Germany, 2008."},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.11.015"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"N. Immerman,\n                      Descriptive Complexity\n                      , Springer, New York, 1999.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00150-1"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"D. J. Kavvadias, C. H. Papadimitriou, and M. Sideri,\n                      On Horn envelopes and hypergraph transversals\n                      , in Algorithms and Computation, 4th International Symposium, ISAAC '93, Hong Kong, 1993, Proceedings, K.W. Ng, P. Raghavan, N. V. Balasubramanian, and F. Y. L. Chin, eds., Lecture Notes in Comput. Sci. 702, Springer, Berlin, 1993, pp. 399-405,https:\/\/doi.org\/10.1007\/3-540-57568-5_271.","DOI":"10.1007\/3-540-57568-5_271"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00346-0"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.04.012"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.09.006"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1016\/j.biosystems.2005.04.009"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btg395"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1000385"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"L. Libkin,\n                      Elements of Finite Model Theory\n                      , Texts Theoret. Comput. Sci. EATES Ser., Springer, Berlin, 2004.","DOI":"10.1007\/978-3-662-07003-1"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90031-5"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1016\/0169-023X(94)90023-X"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009796218281"},{"key":"atypb46","first-page":"211","author":"Mishra N.","year":"1997","journal-title":"New York"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(87)90062-2"},{"key":"atypb48","unstructured":"E. R. Scheinerman and D. H. Ullman,\n                      Fractional Graph Theory: A Rational Approach to the Theory of Graphs\n                      , Wiley, New York, 1997."},{"key":"atypb49","unstructured":"J. Tor\u00e1n,\n                      Structural Properties of the Counting Hierarchies\n                      , Ph.D thesis, Facultat d'lnformatica de Barcelona, Barcelona, 1988."},{"key":"atypb50","doi-asserted-by":"crossref","unstructured":"J. Tor\u00e1n,\n                      Succinct representations of counting problems\n                      , in Proceedings of the 6th International Conference on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 1988, AAECC-6 Rome, Italy, Lecture Notes in Comput. Sci. 357, T. Mora, ed., Springer, Berlin, 1989, pp. 415-426,https:\/\/doi.org\/10.1007\/3-540-51083-4_77.","DOI":"10.1007\/3-540-51083-4_77"},{"key":"atypb51","doi-asserted-by":"crossref","unstructured":"H. Vollmer,\n                      Introduction to circuit complexity\n                      , Texts Theoret. Comput. Sci. EATES Ser., Springer, Berlin, 1999.","DOI":"10.1007\/978-3-662-03927-4"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1027267","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:19:09Z","timestamp":1787339949000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1027267"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/15M1027267"],"URL":"https:\/\/doi.org\/10.1137\/15m1027267","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}