[bxmlt] Uwe Krüger – NPBibSearch, an ontology of NP-complete problems

Posted on September 26, 2006 by Richard Cyganiak

From the problem of the NP-completeness of ontologies, we now move to an ontology of NP-complete problems.

The famous “P = NP?” is one of the big unsolved questions of computer science, with a large body of existing work. The talk is about formalizing the domain of NP-complete problems.

The ontology has classes like “Decision Problem”, “Complexity Class” and “Algorithm”. The ontology was populated with 350 problems from a standard text book on NP-completeness. Instances are annotated with further bibliographical references from some 1000 papers. Everything was entered by hand. (I think.)

Why do this? To assist bibliographical searches. There’s a web interface. (I think it’s supposed to be here, currently down.) In addition to the usual full text search, users can navigate the domain space. The web interface includes a cool widget that shows the current item’s relation to neighbouring items and looks quite usable – a good domain-specific search interface.

Implementation: Jena, servlets, Google/Yahoo API for full text search.

(This is an example of the “80% of Semantic Web projects” Heiner Stuckenschmidt was referring to earlier today. I think the value in this project is the aggregated knowledge collected by a number of experts over years. This would become really interesting if it would be possible to link this with knowledge bases in neighbouring domains maintained by other groups of experts.)

This entry was posted in General, Semantic Web. Bookmark the permalink.

1 Response to [bxmlt] Uwe Krüger – NPBibSearch, an ontology of NP-complete problems

  1. Uwe Krüger says:
    August 3, 2007 at 09:50

    Hi Richard,

    You might remember me (we stand together on the poster session at the
    XML-Tage 2006 in Berlin). I have done this work that you described above
    and I am pleased about your article about this project in your blog. I
    found your blog post now by chance.

    Unfortunately, the link to the application has been changed. Here is the
    new URL: http://www.osotis.com:8080/NPBibSearch/.

    Please spend a view of our newest project, Osotis, a video search engine
    for digitalized lectures and educational videos. For a first impression
    please have a look to our project blog (http://osotis.blogspot.com) or to the search engine
    (www.osotis.com) itself. Osotis provides a couple of functionalities
    around the Web 2.0 idea, e.g. tagging, discussions and wiki. The core
    innovation of this video search engine is the possibility for a
    time-based tagging and search function. Thus, you can search WITHIN the
    content of the videos self.

    Best Regards,
    Uwe.

Comments are closed.