Generating hard tautologies using predicate logic and the symmetric group

DOI10.1093/jigpal/8.6.787zbMath0967.03012OpenAlexW2051226232MaRDI QIDQ4521285

Sitharam, Meera, Søren Riis

Publication date: 3 September 2001

Published in: Logic Journal of IGPL (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/7c7d7f80eff0e13062d200da59f1e38f2de65f08

zbMATH Keywords

satisfiabilitycomplexity theoryfinite model theorypropositional proof complexitypropositional proof systemsymmetric permutation grouphard propositional tautologiessecond-order existential sentences

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Complexity of proofs (03F20)

Related Items (3)

Unnamed Item ⋮ Relativization makes contradictions harder for resolution ⋮ Uniformly generated submodules of permutation modules over fields of characteristic 0.

This page was built for publication: Generating hard tautologies using predicate logic and the symmetric group