Lower Bounds for Existential Pebble Games and k-Consistency Tests

DOI10.1109/LICS.2012.14zbMath1360.68490arXiv1205.0679MaRDI QIDQ5892434

Christoph Berkholz

Publication date: 16 May 2017

Published in: 2012 27th Annual IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1205.0679

zbMATH Keywords

\(k\)-consistencyexistential pebble games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items (1)

Constructing Hard Examples for Graph Isomorphism

This page was built for publication: Lower Bounds for Existential Pebble Games and k-Consistency Tests