liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
On a logical approach to estimating computational complexity of potentially intractable problems
Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab.
2003 (English)In: Proceedings of the 14th International Symposium on Fundamentals of Computation Theory (FCT) / [ed] G. Goos, J. Hartmanis, and J. van Leeuwen, Springer , 2003, Vol. 2751, 423-431 p.Conference paper (Refereed)
Abstract [en]

In the paper we present a purely logical approach to estimating computational complexity of potentially intractable problems. The approach is based on descriptive complexity and second-order quantifier elimination techniques. We illustrate the approach on the case of the transversal hypergraph problem, TRANSHYP, which has attracted a great deal of attention. The complexity of the problem remains unsolved for over twenty years. Given two hypergraphs, G and H, TRANSHYP depends on checking whether G = H-d, where H-d is the transversal hypergraph of H. In the paper we provide a logical characterization of minimal transversals of a given hypergraph and prove that checking whether G subset of or equal to H-d is tractable. For the opposite inclusion the Problem still remains open. However, we interpret the resulting quantifier sequences in terms of determinism and bounded nondeterminism. The results give better upper bounds than those known from the literature, e.g., in the case when hypergraph H, has a sub-logarithmic number of hyperedges and (for the deterministic case) all hyperedges have the cardinality bounded by a function sub-linear wrt maximum of sizes of G and H.

Place, publisher, year, edition, pages
Springer , 2003. Vol. 2751, 423-431 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 2751
Keyword [en]
second-order logic, second-order quantifier elimination, descriptive complexity, transversal hypergraph problem
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-48511DOI: 10.1007/978-3-540-45077-1_39OAI: diva2:269407
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2011-02-25

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Szalas, Andrzej
By organisation
The Institute of TechnologyKPLAB - Knowledge Processing Lab
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 16 hits
ReferencesLink to record
Permanent link

Direct link