scientific article; zbMATH DE number 1522926

zbMATH Open0956.03050MaRDI QIDQ4511222FDOQ4511222

Authors: Shuichi Miyazaki, Kazuo Iwama 

Publication date: 30 October 2000

Title of this publication is not available (Why is that?)

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

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)

Cited In (5)

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

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)