Proofs as Games
From MaRDI portal
Publication:2757489
DOI10.2307/2589349zbMath0983.03045OpenAlexW4241426617MaRDI QIDQ2757489
Publication date: 26 November 2001
Published in: The American Mathematical Monthly (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2589349
Applications of game theory (91A80) Mechanization of proofs and logical operations (03B35) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Complexity of proofs (03F20) Descriptive complexity and finite models (68Q19)
Related Items (21)
Narrow Proofs May Be Maximally Long ⋮ Feasible Interpolation for QBF Resolution Calculi ⋮ Strong ETH and resolution via games and the multiplicity of strategies ⋮ Relativization makes contradictions harder for resolution ⋮ Unnamed Item ⋮ The limits of tractability in resolution-based propositional proof systems ⋮ A game characterisation of tree-like Q-resolution size ⋮ Parameterized proof complexity ⋮ A characterization of tree-like resolution size ⋮ Unnamed Item ⋮ A combinatorial characterization of resolution width ⋮ On exponential time lower bound of Knapsack under backtracking ⋮ Partially definable forcing and bounded arithmetic ⋮ Unnamed Item ⋮ A Game Characterisation of Tree-like Q-resolution Size ⋮ Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space ⋮ Short Proofs Are Hard to Find ⋮ Resolution and the binary encoding of combinatorial principles ⋮ Unnamed Item ⋮ LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE ⋮ Large clique is hard on average for resolution
This page was built for publication: Proofs as Games
