2 votes

Can the initial algebra of a 2-variable polynomial functor be computed on the diagonal?

I finally came up with a proof under the hypotheses of (and thoroughly using) Adamek's fix-point theorem, I'll post it here as soon as I write it down properly. Anyway, I found a bit late that this is ...
sparusaurata's user avatar
2 votes

Power of non-implicationally-complete Frege systems and Boolean equational calculus

$\let\eq\leftrightarrow\def\ru{\mathrel/}\let\ET\bigwedge$Frege systems are required to be implicationally complete to make all such systems p-equivalent, yielding a robust definition of the Frege ...
Emil Jeřábek's user avatar
1 vote

Complexity of solving a higher-order degree polynomial equation? P-problem or NP-problem or neither?

Finding the factorization of a single-variable polynomial with rational coefficients is apparently solvable in poly time, as shown in [1]: [1] Lenstra, A. K.; Lenstra, H. W., Jr.; Lovász, L. Factoring ...
Neal Young's user avatar
  • 10.8k

Only top scored, non community-wiki answers of a minimum length are eligible