Proofs as Games
From MaRDI portal
Applications of game theory (91A80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Mechanization of proofs and logical operations (03B35) Complexity of proofs (03F20) Descriptive complexity and finite models (68Q19) Complexity of computation (including implicit computational complexity) (03D15)
Recommendations
Cited in
(35)- On exponential time lower bound of Knapsack under backtracking
- Resolution and the binary encoding of combinatorial principles
- Game Characterizations and the PSPACE-Completeness of Tree Resolution Space
- The limits of tractability in resolution-based propositional proof systems
- Proof complexity and the binary encoding of combinatorial principles
- Large clique is hard on average for resolution
- A tradeoff between length and width in resolution
- A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games
- Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
- Strong ETH and resolution via games and the multiplicity of strategies
- Lower bounds for DNF-refutations of a relativized weak pigeonhole principle
- Partially definable forcing and bounded arithmetic
- scientific article; zbMATH DE number 7350778 (Why is no real title available?)
- From parity games to circular proofs
- A characterization of tree-like resolution size
- scientific article; zbMATH DE number 7561681 (Why is no real title available?)
- A game characterisation of tree-like Q-resolution size
- Parity Games and Propositional Proofs
- Monotone circuit lower bounds from resolution
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- A combinatorial characterization of resolution width
- Strong ETH and resolution via games and the multiplicity of strategies
- Short Proofs Are Hard to Find
- Proof and refutation in MALL as a game
- A game characterisation of tree-like Q-resolution size
- Feasible interpolation for QBF resolution calculi
- On the Descriptive Complexity of a Simplified Game of Hex
- Parity Games and Propositional Proofs
- Lower bounds for set-blocked clauses proofs
- Proving unsatisfiability with hitting formulas
- Narrow proofs may be maximally long
- Theory and Applications of Satisfiability Testing
- The intractability of resolution
- Relativization makes contradictions harder for resolution
- Parameterized proof complexity
This page was built for publication: Proofs as Games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2757489)
