University of Cambridge > Talks.cam > Computer Laboratory Automated Reasoning Group Lunches > Evaluating Formulas on Graphs

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Evaluating Formulas on Graphs

Download to your calendar using vCal

If you have a question about this talk, please contact Thomas Tuerk .

We consider the computational complexity of the following problem: given a first-order formula f in the language of graphs (i.e. with one binary relation) and a finite graph G, determine whether f is satisfied in G. The complexity is generally exponential in the size of f, though polynomial in the size of G. The problem is quite general and encompasses many known hard decision problems on graphs. I well explain how the problem can be made more tractable on restricted classes of graphs, which will lead us to a brief exploration of graph structure theory.

This talk is part of the Computer Laboratory Automated Reasoning Group Lunches series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Room 1, Mill Lane Lecture Rooms BAS Seminar Room 12 Lecture Room 2 in the gatehouse at INI.

Other talks

From lab to clinic: an introduction to translational research The Neurophenomenology of Surrender: Agency, Renewal, and Social Engagement in Speaking in Tongues Coming soon Title TBC Climate, uncertainty, and the slippery measurement of Antarctic ice Title to be confirmed
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity