Life sciences · Preprint

Fitting and Learning Basis-Restricted Propositional Formulas

arXiv · September 8, 2026

Insufficient Information Why this matters to you Expert discussion

The material analysed did not support any firm read.

AI Summary

This is a theoretical computer science paper that analyzes the computational complexity of fitting and learning propositional formulas built from arbitrary Boolean function bases. It determines complexity classes for various problems (Occam algorithms, empirical risk minimization, PAC learning) as a function of the choice of basis functions, but does not report empirical validation, clinical data, or biological evidence.

What was studied

Preprint.

Key findings

The paper determines complexity of fitting problems, Occam algorithms, empirical risk minimization, and PAC learning for each possible choice of basis Boolean functions O. Results apply to both formula trees and circuits representations. The complexity classification depends on which Boolean functions are included in the basis set O.

Safety

Safety was not reported in the material analysed. Check the source before drawing any conclusion about harm.

Who this may help

The source did not state who this applies to in practice.

Plain-language summary

This is a theoretical computer science paper exploring computational complexity of learning problems for propositional formulas; it raises and addresses questions about fitting and learning algorithms rather than reporting empirical clinical or biological evidence.

Caveats

This is a preprint on arXiv and has not been peer reviewed.
No empirical validation, computational experiments, or benchmarks are reported.
No clinical or biomedical application; purely theoretical computer science.
No concrete complexity results, bounds, or specific complexity classes are stated in the abstract.

Evidence assessment

Graded across the dimensions that decide whether you should act, each from what the source actually supports. There is no single score, and where a dimension was not assessed it says so.

Study design

insufficient

Theoretical complexity analysis; no empirical study design described.

Directness

insufficient

No application to clinical or biological outcome; purely computational.

Consistency

insufficient

No empirical validation or comparison with prior work reported.

Risk of bias

insufficient

Mathematical proofs; bias framework does not apply.

Sample adequacy

insufficient

No empirical sample; theoretical results only.

What is missing. This record has no reported figures. That is a gap in the analysis, not a judgement about the study.

Source abstract

For a finite set $O$ of Boolean functions, we consider the class of propositional formulas built using the functions in $O$ as connectives. We determine, for each possible choice of $O$, the complexity of various fitting and learning problems. These include: finding a formula that fits a given labeled sample, finding a small one (an Occam algorithm), minimizing the number of misclassified examples when the sample is not realizable (empirical risk minimization), and several forms of PAC learning. Our results apply both to formulas (represented as trees) and to circuits. We also briefly discuss the status of the same questions for other kinds of propositional fragments.

Follow from this

Taken from the source record, never inferred. Follow any of these and new work involving them reaches your briefing.

Balder ten Cate