scientific article; zbMATH DE number 1522926

MaRDI QIDQ4511222zbMATH OpenFDO

Authors Shuichi Miyazaki, Kazuo Iwama

Publication date 30 October 2000

zbMATH Keywords

lower boundbacktrackingpigeonhole principleproof sizetree-like resolutionDAG-like resolution

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Recommendations

• A complexity gap for tree resolution
• A tutorial on time and space bounds in tree-like resolution
• A lower bound for tree resolution
• Resolution with counting: dag-like lower bounds and different moduli
• scientific article; zbMATH DE number 7650367
• Computing Tree-Depth Faster Than 2 n
• Computing tree-depth faster than \(2^n\)
• Improved Lower Bounds for Tree-Like Resolution over Linear Inequalities
• Finding a tree structure in a resolution proof is NP-complete
• Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space

Cited in

(5)

• On the decision trees with symmetries
• On the one-way function candidate proposed by Goldreich
• A characterization of tree-like resolution size
• Tight upper bound on splitting by linear combinations for pigeonhole principle
• A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4511222)