commit 073b57210df08ce39420b87bb0652bbaf28b61d0
parent 5bcd0e7a21a6454452ab535c1a81ac8180ec2bfb
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 19 Feb 2025 12:00:21 +0100
commit with codex
Diffstat:
25 files changed, 123 insertions(+), 18 deletions(-)
diff --git a/accepting_run b/accepting_run
@@ -0,0 +1,9 @@
+# Accepting run
+
+A [run] which finishes on a [final_state]
+
+Up: [run]
+
+Aliases: accepting runs
+
+See also: [rejecting_run]
diff --git a/complexity_time b/complexity_time
@@ -1,6 +1,6 @@
# Complexity time
-The [asymptotic] running time of an [algorithm]
+The [asymptotic] [running_time] of an [algorithm]
- [complexity_time_classes]
diff --git a/fagins_theorem b/fagins_theorem
@@ -0,0 +1,5 @@
+# Fagin's theorem
+
+https://en.wikipedia.org/wiki/Fagin%27s_theorem
+
+Up: [theorem], [descriptive_complexity]
diff --git a/fp b/fp
@@ -0,0 +1,5 @@
+# FP
+
+The [complexity_class] of the [functions] computed by [deterministic_Turing_machines] in [polynomial_time]
+
+Up: [complexity_class]
diff --git a/game_theory b/game_theory
@@ -1,10 +0,0 @@
-# Game theory
-
-studies [games]
-
-- [shapley_value]
-- [parity_games] et [pseudopolynomial]-time algorithm
-- [muller_acceptance]
-- [prisoners_dilemma]
-
-Up: [mathematics]
diff --git a/gap_p b/gap_p
@@ -0,0 +1,13 @@
+# GapP
+
+https://complexityzoo.net/Complexity_Zoo:G#gapp
+
+The functions that can be expressed as the [gap] of a [nondeterministic_Turing_machine], aka the difference between the number of [accepting_runs] and of [rejecting_runs]
+
+The closure of the [sharpP] functions under [subtraction]
+
+mentioned in [thierauf1994closure] for instance
+
+Up: [complexity_class]
+
+Aliases: GapP
diff --git a/integers b/integers
@@ -4,4 +4,4 @@ The set \mathbb{Z} of [natural_numbers] or the [negative_numbers] (including [ze
Up: [number]
-Aliases: integer
+Aliases: integer, ZZ
diff --git a/maximum b/maximum
@@ -3,7 +3,7 @@
the largest [element] of an [order]
- [supremum]
-See also: [minimum]
+See also: [minimum], [maximization_problem]
Up: [mathematics_basic_concepts]
diff --git a/minimal_witness b/minimal_witness
@@ -1,5 +1,7 @@
# Minimal witness
+#todo "minimum witness"?
+
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
diff --git a/npmv b/npmv
@@ -0,0 +1,5 @@
+# NPMV
+
+https://complexityzoo.net/Complexity_Zoo:N#npmv
+
+Up: [complexity_class]
diff --git a/parity_p b/parity_p
@@ -6,4 +6,4 @@ https://en.wikipedia.org/wiki/Parity_P
Up: [parity], [complexity_class]
-See also: [parity_fine_grained]
+See also: [parity_fine_grained], [Z_2Z]
diff --git a/partial_run b/partial_run
@@ -0,0 +1,5 @@
+# Partial run
+
+A generalization of [runs], that only process a [prefix] of the input [word]
+
+Up: [run]
diff --git a/ptime b/ptime
@@ -13,4 +13,4 @@ Up: [complexity_class]
See also: [pseudo_polynomial_time], [quasipolynomial], [oplusp], [ptime_reduction]
-Aliases: P
+Aliases: P, polynomial time
diff --git a/rejecting_run b/rejecting_run
@@ -0,0 +1,9 @@
+# Rejecting run
+
+A [run] which finishes at a [nonfinal_state]
+
+See also: [accepting_run]
+
+Up: [run]
+
+Aliases: rejecting runs
diff --git a/run b/run
@@ -0,0 +1,11 @@
+# Run
+
+A [sequence] of [states] that starts by an [initial_state] and follows [configurations] on an input [word]
+
+- [accepting_run]
+- [rejecting_run]
+- [partial_run]
+
+Up: [automata_concepts]
+
+Aliases: runs
diff --git a/second_order_logic b/second_order_logic
@@ -0,0 +1,14 @@
+# SO
+
+- [monadic_second_order_logic]
+- [descriptive_complexity]: correspondence with [polynomial_hierarchy]
+ - [existential_second_order_logic] corresponds to [nptime], etc.,
+ [quantifier_prefix]
+- [second_order_transitive_closure] SO(TC) [ferrarotti2018expressivity]
+ - corresponds to [pspace]
+ - can express [hamiltonian_cycle]
+ - which is known not to be expressible in [monadic_second_order_logic]
+
+See also: [first_order_logic]
+
+Aliases: SO
diff --git a/semiring_idempotent b/semiring_idempotent
@@ -1,6 +1,6 @@
# Idempotent semiring
-A [semiring] satisfying the equation a+a = a for every a ("additively idempotent")
+A [semiring] satisfying the equation a+a = a for every a, i.e., [additively_idempotent]
Not the case of all [semirings], e.g., not the [natural_numbers]
diff --git a/semiring_multiplicative_idempotent b/semiring_multiplicative_idempotent
@@ -1,6 +1,6 @@
# Semiring multiplicative idempotent
-[Semiring] where s s = s for all s
+[Semiring] where s s = s for all s, i.e., [multiplicatively_idempotent]
Generalization: [semiring_n_idempotent]
diff --git a/theorem b/theorem
@@ -6,6 +6,7 @@ A [result] in [mathematics], recognized as challenging to prove
- [Brook's_theorem]
- [Buchi's_theorem]
- [Chen's_theorem]
+- [Codd's_theorem]
- [Context_free_grammar_pushdown_automaton_equivalence]
- [Courcelle_theorem]
- [Eggan's_theorem]
diff --git a/tropical_semiring b/tropical_semiring
@@ -6,8 +6,10 @@ Intuition: you want the derivation with least cost ([min]), and joint use of val
Useful for [shortest_path] in [graphs]
+It is an [absorptive_semiring]
+
Up: [semiring_list]
-See also: [mpp_minimum], [tropical]
+See also: [mpp_minimum], [tropical], [max_plus_semiring]
Aliases: semiring tropical
diff --git a/turing_machine b/turing_machine
@@ -14,6 +14,7 @@
## Variants
- [turing_machine_symmetric]
+- [turing_machine_weighted]
## Resources
@@ -22,3 +23,5 @@
Up: [theoretical_computer_science]
See also: [ram_model], [church_turing_thesis], [alan_turing], [pushdown_automaton], [turing_complete], [decidability], [recursively_enumerable], [kolmogorov_complexity]
+
+Aliases: Turing machines
diff --git a/turing_machine_deterministic b/turing_machine_deterministic
@@ -0,0 +1,11 @@
+# Turing machine deterministic
+
+A [turing_machine] whose [transition_relation] is a [transition_function], so that it has at most one [run] on every input
+
+- [turing_machine_deterministic_ptime]
+
+Up: [turing_machine]
+
+Aliases: deterministic Turing machine, deterministic Turing machines
+
+See also: [turing_machine_nondeterministic]
diff --git a/turing_machine_nondeterministic b/turing_machine_nondeterministic
@@ -1,7 +1,11 @@
# Turing machine nondeterministic
+A [Turing_machine] which may have several applicable [transitions], so that it can have multiple [runs] on an input
+
- [nptime]: [nondeterministic_ptime_turing_machine]
Up: [turing_machine]
Aliases: nondeterministic Turing machine
+
+See also: [turing_machine_deterministic]
diff --git a/turing_machine_weighted b/turing_machine_weighted
@@ -0,0 +1,14 @@
+# Turing machine weighted
+
+[turing_machine_weighted_definition]
+
+They are to [Turing_machines] what [weighted_automata] are to [automata]
+
+Can define [complexity_classes] that are [formal_power_series]: [weighted_language_series_correspondence]
+- see also [weighted_complexity_classes] in [badia2024logical]
+
+Were originally called "algebraic turing machines" in [damm2002complexity], connected to [weighted_automata] in [kostolanyi2023weighted]
+
+Up: [turing_machine], [weighted]
+
+Aliases: Weighted Turing machine, weighted Turing machines
diff --git a/viterbi_semiring b/viterbi_semiring
@@ -4,6 +4,8 @@ The [semiring] defined as ([0, 1], [max], [multiplication], 0, 1)
Intuitively: you want the derivation with highest confidence ([max]), and when you use several values simultaneously then confidence decreases via [multiplication]
+It is an [absorptive_semiring]
+
Up: [semiring_list]
See also: [tropical_semiring]
