MathDB3 problems
- 0 votes0 replies0 views
Nonexistence of a p-optimal proof system for satisfiable propositional formulas
A proof system for a set is p-optimal if it p-simulates every proof system for , where p-simulation means that proofs can be transformed by a polynomial-time function into p…
- 0 votes0 replies0 views
Bonet–Buss–Pitassi's conjecture on the proof complexity of linear algebra identities
Bonet–Buss–Pitassi's conjecture. Frege does not admit polynomial-size proofs of these identities. The conjecture concerns whether the quasi-polynomial Frege proofs obtained from al…
- 0 votes0 replies1 view
Extension of the admissibility results to modal dependence logic and propositional independence logic
Modal dependence logic and propositional independence logic are logics with disjunctive normal forms similar to those used for propositional logics of dependence. Conjecture. The a…