Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata

Basic Information

• Paper ID: 2310.18965
• Title: Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata
• Author: Tomoyuki Yamakami (University of Fukui, Japan)
• Classification: cs.CC (Computational Complexity), cs.FL (Formal Languages and Automata Theory)
• Publication Time/Conference: FCT 2023 (24th International Symposium on Fundamentals of Computation Theory)
• Paper Link: https://arxiv.org/abs/2310.18965

Abstract

Building upon research on nonuniform polynomial-size finite automata families, this paper extends the scope of investigation to partial counting functions and gap functions defined by nondeterministic finite automata, as well as associated promise decision problem families. Counting functions compute the number of accepting computational paths generated by nondeterministic finite automata. Without relying on unproven hardness assumptions, the author establishes numerous separation and collapse relationships between complexity classes of these partial counting and gap function families and their induced promise decision problem families, and investigates their relationships with pushdown automata families under polynomial stack-state complexity.

Research Background and Motivation

1. Core Problem: Investigating the computational power of nonuniform polynomial-size finite automata families, particularly understanding the nature of nondeterminism within the "counting" framework.
2. Significance:
   • Nondeterminism is a core concept in theoretical computer science; understanding its nature is crucial for complexity theory
   • Counting functions and gap functions play important roles in characterizing various complexity classes
   • The theory of nonuniform polynomial state complexity requires further development and refinement
3. Limitations of Existing Approaches:
   • Existing research primarily focuses on decision problems with insufficient investigation of counting functions
   • Lack of systematic separation and collapse results
   • Unclear relationships with other computational models (such as pushdown automata)
4. Research Motivation: By introducing counting and gap functions, comprehensively understand the computational power of nondeterministic finite automata and establish a complete complexity hierarchy.

Core Contributions

1. Introduction of New Function Classes: Defines counting function class 1# and gap function class 1Gap, based on nonuniform polynomial-size nondeterministic finite automata families.
2. Establishment of Complexity Hierarchy: Systematically investigates inclusion and separation relationships among multiple counting complexity classes (1U, 1⊕, 1C=, 1SP, 1P, etc.).
3. Proof of Separation Results: Without relying on unproven assumptions, establishes numerous separations between complexity classes, such as 1N ⊈ 1C=, 1⊕ ⊈ 1P, etc.
4. Closure Property Analysis: Investigates closure properties of function classes under various function operations, proving that 1# is not closed under multiple operations.
5. Relationship with Pushdown Automata: Establishes comparative relationships with pushdown automata families under polynomial stack-state complexity.

Detailed Methodology

Task Definition

This paper investigates the counting capability of nonuniform finite automata families, primarily involving:

• Input: Promise decision problem families {(L_n^(+), L_n^(-))}_n∈ℕ
• Output: Inclusion/separation relationships of complexity classes
• Constraints: Polynomial state complexity restrictions

Model Architecture

1. Basic Definitions

• 1nfa: One-way nondeterministic finite automaton, formally (Q,Σ,{⊢,⊣},δ,q₀,Q_acc,Q_rej)
• State Complexity: sc(M) = |Q|, polynomial-size requirement stipulates existence of polynomial p such that sc(M_n) ≤ p(n)

2. Function Class Definitions

• Counting Function Class 1#: Family of partial functions defined by the number of accepting paths #M_n(x) of 1nfa families
• Gap Function Class 1Gap: Family of partial functions defined by the difference between accepting and rejecting path counts #M_n(x) - #̄M_n(x)

3. Complexity Class Definitions

Multiple complexity classes defined based on counting and gap functions:

• 1U (Unambiguous Class): f_n(x) = 1 for x ∈ L_n^(+), f_n(x) = 0 for x ∈ L_n^(-)
• 1⊕ (Parity Class): f_n(x) is odd for x ∈ L_n^(+), f_n(x) is even for x ∈ L_n^(-)
• 1C= (Exact Counting Class): g_n(x) = 0 for x ∈ L_n^(+), g_n(x) ≠ 0 for x ∈ L_n^(-)
• 1SP (Strict Probability Class): g_n(x) = 1 for x ∈ L_n^(+), g_n(x) = 0 for x ∈ L_n^(-)
• 1P (Probability Class): g_n(x) > 0 for x ∈ L_n^(+), g_n(x) ≤ 0 for x ∈ L_n^(-)

Technical Innovations

1. Branching Normal Form: Introduces Lemma 2.1, converting arbitrary 1nfa into equivalent form making fixed number of nondeterministic choices at each step.
2. Kolmogorov Complexity Technique: Utilizes Kolmogorov complexity to prove separation results, particularly in the proof of Theorem 4.4.
3. Connection with Single-Tape Linear-Time Machines: Establishes connection with advised single-tape linear-time Turing machines through Lemmas 4.10 and 4.15, used to prove key separation results.
4. Probabilistic Finite Automata Characterization: Provides probabilistic finite automata characterization of 1P and 1C= through Lemmas 4.11 and 4.12.

Experimental Setup

Theoretical Verification Methods

This paper is purely theoretical research employing mathematical proof methods:

1. Constructive Proofs: Proving inclusion relationships through constructing specific promise problem families
2. Diagonalization Arguments: Using Kolmogorov complexity for diagonalization proofs of separations
3. Reduction Techniques: Establishing separation relationships through reductions between complexity classes

Key Lemmas and Theorems

• Lemma 2.1 (Branching Normal Form): Standardizes computational structure of 1nfa
• Theorem 4.6: 1N ⊈ 1C= and related separations
• Theorem 4.13: Key separation 1⊕ ⊈ 1P
• Theorem 5.1: Comparison with pushdown automata

Experimental Results

Main Results

1. Complexity Hierarchy Structure

Establishes complete inclusion and separation relationship diagram (Figure 2), with main results including:

• Strict Inclusions: 1D ⊊ 1U ⊊ 1SP, 1U ⊊ 1N, 1C= ⊊ 1P
• Incomparabilities: 1N ⊈ 1C=, 1⊕ ⊈ 1P, co-1U ⊈ 1N

2. Function Class Relationships

• 1FN ⊊ 1# ⊆ 1Gap≥0
• 1Gap = 1# - 1# = 1# - 1FN = 1FN - 1#

3. Closure Properties

• Closed Operations: 1# and 1Gap are closed under addition and multiplication
• Non-Closed Operations: 1# is not closed under minimum, maximum, proper subtraction, integer division, etc.

Key Constructions in Separation Proofs

Theorem 4.4 Proof Highlights

Constructs promise problem family L_U, using Kolmogorov complexity to prove co-1U ⊈ 1N:

• Defines L_n^(+) = {u#v | u,v ∈ B_n(n,n), ∃!e∈[n]((u)_e ≠ (v)_e)}
• Completes proof through compression contradiction of high Kolmogorov complexity strings

Theorem 4.13 Proof Highlights

Constructs L_⊕ family to prove 1⊕ ⊈ 1P:

• Defines promise problem based on bit inner product operation
• Utilizes prefix-suffix separation property of Lemma 4.15

Related Work

Historical Development

1. Sakoda-Sipser Framework (1978): Establishes foundational theory of nonuniform polynomial state complexity
2. Kapoutsis Extensions (2009-2012): Introduces probabilistic and alternating finite automata
3. Yamakami Series: Extensions to quantum, unambiguous, width-restricted, etc.

Connection with Counting Complexity

• Valiant's #P Theory: This paper introduces counting concepts into finite automata settings
• Single-Tape Linear-Time Machines: Establishes connection utilizing Hennie results and Tadaki-Yamakami-Li work
• Advised Complexity: Relationships with advised classes such as 1-C=LIN/lin

Technical Method Comparison

Advantages of this paper compared to related work:

• Systematic separation results without unproven assumptions
• Complete analysis of function class closure properties
• Comparative study with pushdown automata

Conclusions and Discussion

Main Conclusions

1. Establishes complete theoretical framework for counting complexity of nonuniform polynomial-size finite automata families
2. Proves numerous separation relationships between complexity classes, revealing fine-grained hierarchy of counting in finite automata
3. Closure property research of function classes provides new perspective on understanding computational complexity of counting operations

Limitations

1. Computational Model Restrictions: Considers only one-way finite automata; two-way case is more complex
2. Practical Applications: Connection between theoretical results and practical computational problems requires further exploration
3. Completeness: Some relationships in Figure 2 remain undetermined

Future Directions

The author proposes 7 open problems:

1. Complete missing relationships in complexity hierarchy diagram
2. Investigate closure of 1P under union and intersection operations
3. Explore closure properties under more function operations
4. Extended research on k-turn pushdown automata
5. Counting complexity of two-way automata
6. Connections with logarithmic space complexity classes
7. Generalization to weighted automata

In-Depth Evaluation

Strengths

1. Theoretical Depth:
   • Systematically develops counting theory for finite automata
   • Sophisticated proof techniques, particularly application of Kolmogorov complexity and probabilistic methods
   • Establishes profound connections with classical complexity theory
2. Technical Innovation:
   • Introduction of technical tools such as branching normal form
   • Clever utilization of connections with single-tape linear-time machines
   • Characterization methods for probabilistic finite automata
3. Result Completeness:
   • Provides complete complexity hierarchy structure
   • Systematically analyzes closure properties of function classes
   • Separation results without unproven assumptions

Weaknesses

1. Limited Practical Applicability:
   • Pure theoretical research with insufficient connection to practical computational problems
   • Results primarily possess theoretical significance
2. Technical Complexity:
   • Proof techniques are relatively complex with high comprehension threshold
   • Some constructions are somewhat artificial
3. Completeness Issues:
   • Some complexity relationships remain undetermined
   • Certain proofs rely on relatively strong technical assumptions

Impact

1. Academic Contribution:
   • Provides new research direction for finite automata theory
   • Enriches content of counting complexity theory
   • Establishes bridges between multiple research fields
2. Theoretical Value:
   • Deepens understanding of the nature of nondeterminism
   • Provides new analytical tools for complexity theory
   • Inspires subsequent related research
3. Reproducibility: All results are mathematical proofs with complete reproducibility

Applicable Scenarios

1. Theoretical Research: Complexity theory, automata theory, and computational theory research
2. Teaching: Reference material for advanced complexity theory courses
3. Further Research: Provides foundation and tools for subsequent research in related fields

References

The paper includes 44 important references, primarily covering:

• Classical complexity theory literature (Valiant, Sakoda-Sipser, etc.)
• Finite automata state complexity research (Kapoutsis, Geffert, etc.)
• Counting complexity theory (Fenner-Fortnow-Kurtz, Ogiwara-Hemachandra, etc.)
• Author's prior related work (Yamakami series)

This paper represents an important development in counting complexity theory within the finite automata setting, establishing a complete theoretical framework through rigorous mathematical analysis with significant theoretical value for understanding the nature of nondeterministic computation.