Symbolic Listings as Computation

We propose an algebraic model of computation which formally relates symbolic listings, complexity of Boolean functions, and low depth arithmetic circuit complexity. In this model algorithms are arithmetic formula expressing symbolic listings of YES instances of Boolean functions, and computation is...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-03
Main Authors: Hamilton Sawczuk, Gnang, Edinah
Format: Article
Language:English
Subjects:
Algorithms
Arithmetic
Boolean functions
Complexity
Computation
Differential equations
Graphs
Mathematical analysis
Operators (mathematics)
Polynomials
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We propose an algebraic model of computation which formally relates symbolic listings, complexity of Boolean functions, and low depth arithmetic circuit complexity. In this model algorithms are arithmetic formula expressing symbolic listings of YES instances of Boolean functions, and computation is executed via partial differential operators. We consider the Chow rank of an arithmetic formula as a measure of complexity and establish the Chow rank of multilinear polynomials with totally non-overlapping monomial support. We also provide Chow rank non-decreasing transformations from sets of graphs to sets of functional graphs.
ISSN:2331-8422