commit 989381965351c4a511950fad2c08bb8e92b38a39
parent 45aaf30ce16ec43f384d9aaa6aa6fceb876e161c
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 14 Nov 2025 11:07:06 +0100
commit with codex
Diffstat:
22 files changed, 99 insertions(+), 57 deletions(-)
diff --git a/addition_chain b/addition_chain
@@ -0,0 +1,13 @@
+# Addition chain
+
+https://en.wikipedia.org/wiki/Addition_chain
+
+It is not known to be [NP_hard]
+- cf https://math.stackexchange.com/a/109905
+- however the [addition_sequence] problem is [NP_hard]
+
+Variant: [addition_subtraction_chain]
+
+See also: [minimum_circuit_size_problem], [carry], [Smallest_grammar_problem]
+
+Up: [theoretical_computer_science]
diff --git a/addition_sequence b/addition_sequence
@@ -0,0 +1,9 @@
+# Addition sequence
+
+Studied in [downey1981computing]
+
+The problem of finding the smallest number of additions to compute, starting with 1, an input set of integers (whereas [addition_chain] asks this question for a single integer)
+
+Shown [NP_hard] in [downey1981computing]
+
+Up: [addition_chain]
diff --git a/addition_subtraction_chain b/addition_subtraction_chain
@@ -0,0 +1,5 @@
+# Addition subtraction chain
+
+https://en.wikipedia.org/wiki/Addition-subtraction_chain
+
+Up: [addition_chain]
diff --git a/automata b/automata
@@ -10,6 +10,7 @@ https://en.wikipedia.org/wiki/Finite-state_machine
- [automata_constructions]
- [automata_evaluation]
- [automata_classes]
+- [automata_number]
Up: [theoretical_computer_science], [formal_language_theory]
diff --git a/automata_evaluation b/automata_evaluation
@@ -2,11 +2,17 @@
Given an [automaton] A and a [word] w, determine if A accepts w
-- for [DFAs]: can be done in O(|w|), simply by following [transitions]
-- for [NFAs]: can be done in O(|w| |A|) by [state_set_simulation]
+- for [DFAs]: [DFA_acceptance]
+ - can be done in O(|w|), simply by following [transitions]
+- for [NFAs]: [NFA_acceptance]
+ - can be done in O(|w| |A|) by [state_set_simulation]
- [conditional_lower_bound] in [backurs2016which]
- reduction from [OV_conjecture]
- [automata_evaluation_practice]
-Up: [automata_problems]
+See also: [regular_language_membership], [amarilli2025linear]
+
+Aliases: automaton membership, automata membership, automaton acceptance, automata acceptance, automaton evaluation
+
+Up: [automata_problems], [regular_language_membership]
diff --git a/automata_number b/automata_number
@@ -0,0 +1,9 @@
+# Automata number
+
+Number of distinct [formal_languages] accepted by [automata]
+
+Studied in [domaratzki2002number]
+
+Up: [automata]
+
+See also: [Automata_random]
diff --git a/automata_problems b/automata_problems
@@ -1,15 +1,31 @@
# Automata problems
-- [synchronizing_word]
-- [separating_automaton]
-- [automaton_finiteness]
+On one [automaton]:
+
- [automaton_emptiness]
- [universality_automata]
-- [minimization_automaton]
+- [automaton_finiteness]
+- [automaton_cofiniteness]
+- [synchronizing_word_problem]
+- [counter_freeness_testing]
+
+On two [automata]:
+
- [automaton_inclusion]
- [automaton_equivalence]
-- [automaton_cofiniteness]
-- [automata_evaluation]
- [automaton_acceptance]
+On an [automaton] and a [word]:
+
+- [automata_evaluation]
+
+Computation problems:
+
+- [minimization_automaton]
+
+Computing an [automaton] given [words]:
+
+- [separating_automaton]
+- [automaton_from_examples]
+
Up: [automata]
diff --git a/automaton_acceptance b/automaton_acceptance
@@ -1,13 +0,0 @@
-# Automaton acceptance
-
-Given [automaton] A and [word] w, [decide] if A accepts w
-
-- [NFA_acceptance]: [state_set_simulation]
-
-[lower_bounds] from [ov_conjecture], see [backurs2016which]
-
-Up: [automata_problems], [membership_problem]
-
-See also: [regular_language_membership], [amarilli2025linear]
-
-Aliases: automaton membership, automata membership
diff --git a/bpp b/bpp
@@ -1,25 +0,0 @@
-# BPP
-
-Class BPP: [algorithm_randomized] for [decision_problem] with [two_sided_error] can err in both directions with proba 1/4. The error probability can be made exponentially small by retrying
-
-It is known that [PTIME] is included in BPP; the converse implication is not known
-
-it is not known if BPP is contained in [nptime]
-
-It is known that if [nptime] subseteq BPP then in fact [nptime] = [rp] : if you have an
-efficient algorithm for a NP problem that errs in both directions, then in fact
-you can remove errors on one side (uses [self_reducibility])
-
-[sipser_lautemann_theorem]: It is known that BPP is in [sigma2_cap_pi2]: https://en.wikipedia.org/wiki/Sipser%E2%80%93Lautemann_theorem
-- as BPP is closed under [complementation] it suffices to show that it is in [sigma2]
-
-Analogue [BPL] with logarithmic space condition
-
-Corresponding notion of [algorithm] running in [ptime]: "[monte_carlo_algorithm] with bounded probability of two-sided error"
-
-Generalization [pp], with [two_sided_error] and there is no constant bound on how the probability differs in the case of a YES instance and of a NO instance https://en.wikipedia.org/wiki/PP_(complexity)
-- cf [isolated_cut_point]
-
-Up: [complexity_random]
-
-See also: [rp], [automaton_monte_carlo_two_sided], [monte_carlo_algorithm]
diff --git a/counter_free_automata b/counter_free_automata
@@ -4,6 +4,8 @@
Such automata recognize the [aperiodic_languages]
+[decision_problem]: [counter_freeness_testing]
+
Up: [automata_classes]
-Aliases: automata counter-free, automata counter free
+Aliases: automata counter-free, automata counter free, automaton counter free
diff --git a/graph_square_hamiltonian b/graph_square_hamiltonian
@@ -2,8 +2,7 @@
An [undirected_graph] whose [graph_square] is a [Hamiltonian_graph]
-The [recognition_problem] is [NP_hard]
-- cf https://en.wikipedia.org/wiki/Graph_power#Computational_complexity
+The [recognition_problem] is [NP_hard], cf [underground1978graphs]
Up: [graph_square]
diff --git a/isomorphism b/isomorphism
@@ -4,6 +4,7 @@
- [quantum_isomorphism]
- [fractional_isomorphism]
- [group_isomorphism]
+- [isomorphism_problem]
Up: [mathematics]
diff --git a/isomorphism_problem b/isomorphism_problem
@@ -0,0 +1,7 @@
+# Isomorphism problem
+
+The [decision_problem], given two objects in some class, of deciding whether they are [isomorphic]
+
+- [graph_isomorphism_problem]
+
+Up: [decision_problem], [isomorphism]
diff --git a/membership_problem b/membership_problem
@@ -2,6 +2,7 @@
given [formal_language] L description and [word] w, test if w belongs to L
+- [automaton_membership]
- [regular_language_membership]
- [pattern_language_membership]
- [context_free_language_membership]
diff --git a/pointer_chasing b/pointer_chasing
@@ -0,0 +1,5 @@
+# Pointer chasing
+
+studied in [ponzio2001communication], recent bounds in [fischer2025pointer]
+
+Up: [communication_complexity]
diff --git a/regular_language_membership b/regular_language_membership
@@ -1,6 +1,6 @@
# Regular language membership
-- [automaton_acceptance]
+- [automaton_membership]
- [approximate_membership]
- [dynamic_membership]
- [regular_expression_matching]
diff --git a/simple_regular_expressions b/simple_regular_expressions
@@ -23,4 +23,4 @@ Conjunctive Regular Path Queries"
Up: [regular_expression]
-Aliases: SRE
+Aliases: SRE, simple regular expression
diff --git a/simple_transitive_expressions b/simple_transitive_expressions
@@ -4,6 +4,6 @@ Restricted case of [regular_expressions] covering [regular_expression_practice]
Introduced in [martens2018evaluation]
-Up: [regular_expression]
+Up: [simple_regular_expression]
Aliases: simple transitive expression, STE, STEs
diff --git a/smallest_grammar_problem b/smallest_grammar_problem
@@ -6,8 +6,10 @@ The [computational_problem] of finding the smallest [CFG], in various contexts:
- for [finite_languages]: the smallest [CFG] that generates a specific set of [words]
- it is [np_complete]
- studied in [charikar2005smallest]
-- for for [infinite_languages], cf [bucher1981concise]
+- for [infinite_languages], cf [bucher1981concise]
+
+Related: https://cstheory.stackexchange.com/questions/11747/minimal-number-of-symbols-in-context-free-grammar-for-a-special-one-letter-langu
Up: [minimization] of [context_free_grammar]
-See also: [grammar_compression], [straight_line_program], [minimum_circuit_size_problem]
+See also: [grammar_compression], [straight_line_program], [minimum_circuit_size_problem], [addition_chain]
diff --git a/smallest_witness b/smallest_witness
@@ -4,7 +4,7 @@ Find the smallest subset of a [relational_database] that satisfies a [query]
- formally, for query Q and database D, find smallest subset D' of D giving the same result
- [approximation]: find a subset of tuples giving the same results which is within a [approximation_multiplicative] factor of the size of the optimal subset
-easy for [conjunctive_query_full], so hardness comes from [projection]
+easy for [full_CQs], so hardness comes from [projection]
- [miao2019explaining], with [ptime] algorithm for a specific tuple
- [hu2023finding], [best_paper_award] at [icdt_2024]
diff --git a/synchronizing_word b/synchronizing_word
@@ -4,4 +4,4 @@
Up: [automata]
-See also: [mortal_word], [meeting_time], [synchronizing_sets]
+See also: [mortal_word], [meeting_time], [synchronizing_sets], [synchronizing_word_problem]
diff --git a/zpp b/zpp
@@ -5,6 +5,10 @@ ZPP (zero-error probabilistic PTIME) = [rp] cap [corp]
Corresponding algorithms for [ptime]: "Las Vegas" algorithm
+We know that:
+- ZPP contains [PTIME]
+- ZPP is contained in [RP] and in [coRP], which are both contained in [BPP]
+
Up: [complexity_random]
See also: [bpp], [rp], [automaton_las_vegas]
