commit d7e7102aff63f16d48f724306da516db8357f187 parent f4ac2c547cdc038859119f6fa3769e77a4f7df7f Author: Antoine Amarilli <a3nm@a3nm.net> Date: Wed, 1 Apr 2026 23:43:14 +0200 Merge remote-tracking branch 'origin/master' Diffstat:
69 files changed, 290 insertions(+), 51 deletions(-)
diff --git a/acc b/acc @@ -1,6 +1,6 @@ # Acc -Like [ac] circuits, so polynomial size unbounded [fan_in] and [depth] in O(log^i n), but adds gates that can count modulo a fixed integer +Like [ac] circuits, so polynomial size unbounded [fan_in] and [depth] in O(log^i n), but adds [modulo_gates] that can count modulo a fixed integer - contains [parity] - [acc0]: constant [depth] diff --git a/acc0 b/acc0 @@ -1,9 +1,11 @@ -# Acc0 +# ACC0 -[acc] circuit with constant [depth] +[ACC] circuit with constant [depth] -strict superset of [ac0], separated by [parity] +strict superset of [AC0], separated by [parity] -Up: [acc] +Shown by [Ryan_Williams] that there is a problem in [NEXP] which is not in (non-uniform) [ACC0] -See also: [ac0] +Up: [ACC] + +See also: [AC0], [modulo_gates] diff --git a/access_pattern b/access_pattern @@ -2,9 +2,9 @@ [academic_papers]: -- [kara2022conjunctive] [incremental_maintenance] +- [kara2022conjunctive] and [kara2025conjunctive]: [incremental_maintenance] - [zhao2023space]: [complexity_space] vs [complexity_time] tradeoff Up: [database_theory] -Aliases: access patterns +Aliases: access patterns, access method, access methods diff --git a/automata_min_plus b/automata_min_plus @@ -0,0 +1,13 @@ +# Min-plus automata + +[Weighted_automata] in the [tropical_semiring] + +The [deterministic_automata] in this model are less powerful than the [nondeterministic_automata] + +It is [decidable] whether an input min-plus automata is equivalent to a [deterministic_automaton] in this setting, cf [almagor2025determinization] and [almagor2026complexity] + +Up: [automata_weighted] + +See also: [min_plus_matrix_multiplication], [Tropical_semiring] + +Aliases: minplus automata, min plus automata, minplus automaton, min plus automaton diff --git a/automata_weighted b/automata_weighted @@ -18,6 +18,8 @@ Schützenberger, 1961 - [automata_weighted_conjugacy] +- [automata_min_plus] + Up: [automata] See also: [weighted_mso] diff --git a/axiom b/axiom @@ -4,4 +4,4 @@ The initial [nonterminal] of a [context_free_grammar] Up: [context_free_grammar] -See also: [initial_state] +See also: [initial_state], [reverse_mathematics] diff --git a/binary_relation b/binary_relation @@ -0,0 +1,7 @@ +# Binary relation + +A [relation] of [arity] two + +Up: [relation] + +See also: [FO2], [unary_relation] diff --git a/buchis_theorem b/buchis_theorem @@ -6,6 +6,6 @@ Equivalence of [monadic_second_order_logic] and of [regular_languages] for [logi Up: [theorem] in [formal_language_theory] -See also: [Büchi_automaton] +See also: [Büchi_automaton], [trakhtenbrot's_theorem] Aliases: Büchi Elgot Trakhtenbrot theorem diff --git a/circle_graph b/circle_graph @@ -0,0 +1,9 @@ +# Circle graph + +https://en.wikipedia.org/wiki/Circle_graph + +[intersection_graph] of a set of [chords] in a [circle] + +can be recognized in [linear_time], cf [paul2026circle] + +Up: [graph_family] diff --git a/completely_reachable_automata b/completely_reachable_automata @@ -0,0 +1,9 @@ +# Completely reachable automata + +An [automaton] where every nonempty subset of states can be achieved by applying some word on the set of all states + +See [ferens2026recognizing] + +See also: [cerny_conjecture] + +Up: [automata] diff --git a/conjunctive_query_signed b/conjunctive_query_signed @@ -7,6 +7,6 @@ a [conjunctive_query] with [negation] on some [atoms] - [fink2016dichotomies] - [enumeration_cqs]: see [segoufin2015constant] which cites [brault2014pertinence] -Up: [conjunctive_query] with [negation] +Up: [conjunctive_query], [queries_with_negation] See also: [hypergraph_signed] diff --git a/decidable_fo_fragments b/decidable_fo_fragments @@ -0,0 +1,13 @@ +# Decidable FO fragments + +[FO_fragments] for which [satisfiability_FO] is [decidable] + +cf survey [hustadt2004survey] +- [fluted_fragment], cf [fluted_fragment_satisfiability] +- [Maslovs_fragment] alias "K-bar" +- [guarded_fragment], cf [guarded_fragment_satisfiability] +- [FO2], cf [FO2_satisfiability] + +Up: [FO_fragments], [satisfiability_FO] + +Aliases: decidable FO fragment diff --git a/description_logics b/description_logics @@ -5,7 +5,10 @@ A set of lightweight [logics] with different complexity depending on the feature [Survey_paper]: [artale2009dllite] Classes: -- [DL-Lite] +- [DL_Lite] + - [DL_Lite_F] + - [DL_Lite_FR] + - [DL_Lite_FR] - [ALC] - conjunctions imply disjunctions - can use existentials in [rule_head] and [rule_body] diff --git a/directed_acyclic_graph b/directed_acyclic_graph @@ -1,9 +1,11 @@ # Directed acyclic graph (DAG) -[graph_directed] which does not contain [cycle] +[directed_graph] which does not contain a [cycle] -- [topological_sorting] +We can apply [topological_sorting] on such graphs -Up: [graph_directed] +Up: [directed_graph], [acyclic_graph] Aliases: DAG, DAGs + +See also: [SLP_compressed_tree] diff --git a/distance b/distance @@ -7,3 +7,5 @@ - [ultrametric] Up: [mathematics] + +See also: [metric_space] diff --git a/enumeration b/enumeration @@ -21,6 +21,7 @@ https://en.wikipedia.org/wiki/Enumeration_algorithm - [enumeration_diversity] - [enumeration_ordered] - [incremental_maintenance_enumeration] +- [enumeration_practice] Up: [algorithms] diff --git a/enumeration_tasks b/enumeration_tasks @@ -22,5 +22,6 @@ - [enumeration_csp] ([christoph_berkholz]) - [enumeration_topological_sort] - https://cstheory.stackexchange.com/questions/36334/enumerating-topological-sorts-of-a-vertex-labeled-dag +- [enumeration_valuations] Up: [enumeration] diff --git a/equality_generating_dependency b/equality_generating_dependency @@ -7,3 +7,5 @@ A [database_dependency] in which the head is an [equality] [atom] Up: [database_dependency], [first_order_logic] Aliases: EGD, EGDs + +See also: [equality_relation] diff --git a/exact_matching b/exact_matching @@ -5,6 +5,8 @@ [maalouly2022exact]: this is in [RP] and not known to be in [ptime] -Variant: [exact_matching_parity] +Variants: +- [exact_matching_parity] +- [red_blue_yellow_matching] Up: [matching] diff --git a/exogenous_facts b/exogenous_facts @@ -0,0 +1,9 @@ +# Exogenous facts + +A [database_fact] which is assumed to be always present and irremovable (for [smallest_witness] / [resilience] / [explanations] / [responsibility_measures] / etc.) + +See also: [exogenous_relations], [endogenous_facts] + +Up: [facts] + +Aliases: exogenous fact, exogenous diff --git a/exogenous_relations b/exogenous_relations @@ -0,0 +1,9 @@ +# Exogenous relations + +A [relation] where all facts are [exogenous_facts] + +See also: [resilience_csp] + +Up: [relation] + +Aliases: exogenous relation diff --git a/exptime b/exptime @@ -8,4 +8,4 @@ in 2^{P(n)} for P a [polynomial] Up: [complexity_time_classes] -See also: [2exptime], [EXPTIME_complete], [nexptime] +See also: [2exptime], [EXPTIME_complete], [NEXPTIME] diff --git a/first_order_interpretation b/first_order_interpretation @@ -15,4 +15,4 @@ Up: [logic_interpretation], [FO] Aliases: FO interpretation, FO reduction -See also: [FO_projection] +See also: [FO_projection], [MSO_interpretation] diff --git a/fo2 b/fo2 @@ -1,4 +1,4 @@ -# Fo2 +# FO2 [FOk] with [two_variables] @@ -6,9 +6,11 @@ extensions: - [c2] with [counting_quantifier] - [gc2] with [guarded_fragment] quantification -FO2 on [words] with order cannot define [successor]: you need [fo3] +FO2 on [words] with order cannot define [successor]: you need [FO3] - with [successor], it defines a variety of [semigroups] Does not enjoy [craig_interpolation], according to [cate2023craig], but enjoys [finite_model_property] +For [FO_satisfiability], cf [FO2_satisfiability] + Up: [fok] diff --git a/fo3 b/fo3 @@ -0,0 +1,7 @@ +# FO3 + +[first_order_logic] with three variables + +Up: [fok] + +See also: [FO2] diff --git a/fok b/fok @@ -6,7 +6,8 @@ Also called "finite variable logics" in the [survey] [grohe1998finite] ## Fragments -- [fo2] +- [FO2] +- [FO3] ## Extensions diff --git a/graph_family b/graph_family @@ -12,7 +12,9 @@ A (generally [infinite]) set of [graphs] - [multitree] - [forest] - [bipartite_graph] -- [interval_graph] +- [intersection_graph] + - [interval_graph] + - [circle_graph] - [graph_regular] - [graph_cubic] - [grid_graph] diff --git a/hamiltonian_path b/hamiltonian_path @@ -6,6 +6,6 @@ A graph that has such a path is a [Hamiltonian_graph] [Computational_problem]: [Hamiltonian_path_problem] -See also: [hamiltonian_cycle], [traveling_salesperson_problem], [k_path], [path_length], [eulerian_path] +See also: [hamiltonian_cycle], [traveling_salesperson_problem], [k_path], [path_length], [eulerian_path], [3_hamiltonian_path] Up: [path] diff --git a/hyperclique_hypothesis b/hyperclique_hypothesis @@ -6,8 +6,8 @@ For any k >= 3, detecting a k-[hyperclique] in a (k-1)-[uniform_hypergraph] cann - implies in particular [triangle_detection_conjecture]: you cannot detect triangles in O(n^2) in graphs -Up: [hypergraph] +Up: [hypergraph], [complexity_hypothesis] -Aliases: hyperclique conjecture +Aliases: hyperclique conjecture, hyperclique assumption See also: [clique_problem] diff --git a/integrity_constraint b/integrity_constraint @@ -22,4 +22,4 @@ See also: [logic] Up: [databases] -Aliases: integrity constraints +Aliases: integrity constraints, database constraint, database constraints diff --git a/intersection_graph b/intersection_graph @@ -0,0 +1,8 @@ +# Intersection graph + +https://en.wikipedia.org/wiki/Intersection_graph + +- [interval_graph] +- [circle_graph] + +Up: [graph_family] diff --git a/interval_graph b/interval_graph @@ -4,3 +4,5 @@ - [unit_interval_graph] Up: [graph_family], [interval] + +See also: [circle_graph] diff --git a/logic b/logic @@ -74,6 +74,6 @@ Up: [mathematics], [theoretical_computer_science] -See also: [knowledge_representation], [reasoning], [logic_applications], [expressiveness] +See also: [knowledge_representation], [reasoning], [logic_applications], [expressiveness], [reverse_mathematics] -Aliases: logics +Aliases: logics, logical diff --git a/logspace b/logspace @@ -8,7 +8,7 @@ Variant [polyl]: solved with [polylogarithmic] [complexity_space] Variant [NL] ([nondeterminism]) -Variant [SL]: symmetric logspace, class of problems reducible to undirected [reachability], showed to be equal to [logspace] by [reingold] +Variant [SL]: symmetric logspace, class of problems reducible to [undirected_reachability], showed to be equal to [logspace] by [reingold] - for [2sat] corresponds to the case where exactly one literal in each clause must hold Up: [complexity_class] diff --git a/lowest_common_ancestor_problem b/lowest_common_ancestor_problem @@ -2,6 +2,7 @@ Given two [nodes] in a [tree], find their [LCA] -A [tree] can be [preprocessed] in [linear_time] to support such queries in [constant_time], cf for instance https://en.wikipedia.org/wiki/Tarjan%27s_off-line_lowest_common_ancestors_algorithm +A [tree] can be [preprocessed] in [linear_time] to support such queries in [constant_time] +- cf https://en.wikipedia.org/wiki/Tarjan%27s_off-line_lowest_common_ancestors_algorithm Up: [computational_problem], [lowest_common_ancestor] diff --git a/metacomplexity b/metacomplexity @@ -5,3 +5,5 @@ https://simons.berkeley.edu/programs/Meta-Complexity2023 Complexity of problems where we ask what is the complexity of an input, e.g., [kolmogorof_complexity], [minimum_circuit_size_problem] Up: [computational_complexity] + +See also: [reverse_mathematics] diff --git a/nc1 b/nc1 @@ -1,13 +0,0 @@ -# NC1 - -https://en.wikipedia.org/wiki/NC_(complexity) - -circuits with [polynomial] [circuit_size] and [polylogarithmic] [depth] - -NC1 circuits equivalent to polynomial-size uniform family of [formula_boolean] - -https://en.wikipedia.org/wiki/NL_(complexity) says we have: - -[nc1] included in [logtime] included in [nlogtime] included in [nc2] - -Up: [nc], [circuit_complexity] diff --git a/nexptime b/nexptime @@ -0,0 +1,9 @@ +# NEXPTIME + +[nondeterministic] [EXPTIME] + +See also: [EXPTIME] + +Up: [complexity_time_classes] + +Aliases: NEXP diff --git a/preorder b/preorder @@ -0,0 +1,9 @@ +# Preorder + +https://en.wikipedia.org/wiki/Preorder + +A [binary_relation] which is [transitive] and [reflexive] but not necessarily [antisymmetric] + +May be [total_relation] or not, if it is total then it is a [total_order] except that there are "ties" + +Up: [ddal_seminar_vincent] diff --git a/pseudorandomness b/pseudorandomness @@ -1,5 +1,6 @@ # Pseudorandomness - [prng] +- [hardness_vs_randomness] Up: [randomness] diff --git a/quantifier b/quantifier @@ -4,6 +4,7 @@ - [universal_quantifier] - [quantifier_rank] +- [quantifier_prefix] Up: [logic] diff --git a/query_evaluation b/query_evaluation @@ -18,6 +18,8 @@ - [approximate_query_evaluation] - [query_approximation] +- [query_evaluation_constraints] +- [query_evaluation_constraint_satisfaction] Up: [database_theory_problem] diff --git a/query_evaluation_constraint_satisfaction b/query_evaluation_constraint_satisfaction @@ -0,0 +1,5 @@ +# Query evaluation constraint satisfaction + +cf [deeds2026query] + +Up: [query_evaluation], [constraint_satisfaction_problem] diff --git a/query_evaluation_tgds b/query_evaluation_tgds @@ -0,0 +1,7 @@ +# Query evaluation under TGDs + +cf [carmeli2026lets] + +Up: [query_evaluation_constraints], [TGDs] + +Aliases: Query evaluation under TGDs diff --git a/reachability b/reachability @@ -4,6 +4,7 @@ - [st_reachability_undirected] - [reachability_single_source] - [reachability_all_pairs] +- [VASS_reachability] Up: [computational_problem], [graph_theory] diff --git a/red_blue_yellow_matching b/red_blue_yellow_matching @@ -0,0 +1,5 @@ +# Red blue yellow matching + +Variant of [exact_matching] with 3 colors, studied in [aprile2026red] + +Up: [exact_matching] diff --git a/reflexive_relation b/reflexive_relation @@ -0,0 +1,5 @@ +# Reflexive relation + +A [relation] which satisfies [reflexivity] + +Up: [relation] diff --git a/regular_language_polyslender b/regular_language_polyslender @@ -0,0 +1,7 @@ +# Regular language polyslender + +A [regular_language] which is [language_polyslender] + +See [szilard1992characterizing] and [mathematical_foundations_of_automata_theory] Chapitre XII Section 4.2 + +Up: [language_polyslender] diff --git a/relation b/relation @@ -1,6 +1,15 @@ # Relation - [equivalence_relation] +- [preorder] - [word_relation] +- [binary_relation] +- [unary_relation] + +Axioms: +- [transitive_relation] +- [reflexive_relation] +- [symmetric_relation] +- [antisymmetric_relation] Up: [mathematics] diff --git a/satisfiability b/satisfiability @@ -10,6 +10,6 @@ The *satisfiability problem* is a [decision_problem] in [logic]: given a [logica Tools: [sat_solver] -See also: [strong_exponential_time_hypothesis], [satisfiability_boolean], [tautology], [automaton_emptiness], [satisfiability_modulo_theory], [equisatisfiability] +See also: [strong_exponential_time_hypothesis], [satisfiability_boolean], [tautology], [automaton_emptiness], [satisfiability_modulo_theory], [equisatisfiability], [enumeration_valuations], [satisfiability_finite] Up: [computational_problem] diff --git a/satisfiability_finite b/satisfiability_finite @@ -0,0 +1,10 @@ +# Finite satisfiability + +Like [satisfiability] but deciding whether a [logic_formula] has a [finite_model] + +- [finite_model_property] +- [finite_controllability] + +Up: [satisfiability] + +Aliases: finite satisfiability, finsat diff --git a/self_join b/self_join @@ -7,6 +7,6 @@ A *self join* means reusing the same [database_relation] twice in [conjunctive_q Up: [conjunctive_query], [join] -See also: [sjfcq], [conjunctive_query_self_join_free] +See also: [sjfcq], [conjunctive_query_self_join_free], [self_join_freeness] Aliases: self joins, self-join, self-joins diff --git a/shapley_value b/shapley_value @@ -1,5 +1,9 @@ # Shapley value +https://en.wikipedia.org/wiki/Shapley_value + +[shapley_value_definition] + [survey_papers]: - [bertossi2024shapley] - [luo2024applications] @@ -17,3 +21,5 @@ Results: [Computational_problem]: [Shapley_value_computation] See also: [pqe], [explainability], [shap_score], [stable_marriage] + +Up: [responsibility_values] diff --git a/sjfcq b/sjfcq @@ -8,6 +8,6 @@ Special cases: - [acyclic_SJFCQ] - [boolean_SJFCQ] -Up: [conjunctive_query], [self_join] +Up: [conjunctive_query], [self_join_freeness] Aliases: self join free CQ, self join free CQs, selfjoin free CQ, selfjoin free CQs, cq self join free, cqs self join free, self-join-free CQ, self-join-free CQs, conjunctive query self join free, SJFCQs, self join free query, self join free queries diff --git a/st_reachability_undirected b/st_reachability_undirected @@ -2,8 +2,9 @@ Given an [undirected_graph] and two [vertices] s and t, decide if there is an [undirected_path] between s and t -[Complete] for [SL] +[Complete] for [SL], and shown in [L] by [reingold2008undirected]; but open if +[L] = [RL] Up: [st_reachability] -Aliases: undirected st-reachability +Aliases: undirected st-reachability, undirected reachability diff --git a/straight_line_program b/straight_line_program @@ -6,6 +6,8 @@ essentially a [context_free_grammar] that generates a single [string]: [acyclici - [smallest_grammar_problem] - [slp_balancing] +Generalization: [SLP_compressed_trees] + Up: [string_compression] See also: [forest_straight_line_program] diff --git a/suffix_free_language b/suffix_free_language @@ -2,6 +2,8 @@ A [formal_language] L is *suffix-free* if, whenever u and v are in L and u is a [suffix] of v, then u = v +[State_complexity] of suffix-free languages: cf [han2009state] + Up: [suffix] See also: [prefix_free_language], [bifix_free_language] diff --git a/symmetric_relation b/symmetric_relation @@ -0,0 +1,5 @@ +# Symmetric relation + +A [binary_relation] which is symmetric, i.e., forall x y R(x, y) -> R(y, x) + +Up: [relation] diff --git a/transitive_relation b/transitive_relation @@ -0,0 +1,9 @@ +# Transitive relation + +A [relation] which satisfies [transitivity] + +Up: [transitivity] + +Aliases: transitive relations, transitive + +See also: [Transitivity_assertion] diff --git a/transitivity_assertion b/transitivity_assertion @@ -0,0 +1,7 @@ +# Transitivity assertion + +The [logical] assertion that a relation is [transitive] + +Up: [transitivity], [axiom] + +Aliases: transitivity axiom, transitivity axioms, transitivity assertions diff --git a/traveling_salesperson_problem b/traveling_salesperson_problem @@ -0,0 +1,11 @@ +# Traveling salesperson problem + +https://en.wikipedia.org/wiki/Travelling_salesman_problem + +[approximation] when the [distances] correspond to a [metric_space]: +- [Christofides_algorithm] https://en.wikipedia.org/wiki/Christofides_algorithm +- slight approximation in [karlin2023slightly] + +See also: [chinese_postman_problem] + +Up: [computational_problem] on [graphs] diff --git a/tree b/tree @@ -73,6 +73,7 @@ - [multitree] - [out_tree] as a [directed_graph] - [tree_weighted] +- [SLP_compressed_tree] Up: [data_structure] diff --git a/treedepth b/treedepth @@ -4,4 +4,6 @@ https://en.wikipedia.org/wiki/Tree-depth The *treedepth* of an [undirected_graph] G is the minimum [forest_height] of an [elimination_forest] for G +Generalization: [weighted_treedepth] + Up: [width_measure] diff --git a/treedepth_weighted b/treedepth_weighted @@ -0,0 +1,7 @@ +# Weighted treedepth + +Can be [NP_complete], cf [dirks2025weighted] + +Up: [treedepth] + +Aliases: Weighted treedepth diff --git a/tropical_semiring b/tropical_semiring @@ -10,6 +10,6 @@ It is an [absorptive_semiring] Up: [semiring_list] -See also: [mpp_minimum], [tropical], [max_plus_semiring] +See also: [mpp_minimum], [tropical], [max_plus_semiring], [Min_plus_matrix_multiplication], [automata_min_plus] Aliases: semiring tropical, min plus semiring, semiring min plus diff --git a/tseytin_transformation b/tseytin_transformation @@ -7,3 +7,5 @@ Transform a [Boolean_circuit] into [equisatisfiable] [CNF], by adding some addit Up: [circuit] Aliases: Tseytin transform + +See also: [scott_normal_form] diff --git a/tuple_generating_dependency_full b/tuple_generating_dependency_full @@ -0,0 +1,7 @@ +# Full TGD + +A [TGD] with no [existential_quantifiers] + +Up: [tuple_generating_dependency] + +Aliases: Full TGD, Full TGDs, full tuple generating dependency, full tuple generating dependencies, TGD full diff --git a/ultrametric b/ultrametric @@ -3,3 +3,5 @@ [metric] satisfying [triangle_inequality_strong] Up: [distance] + +See also: [metric_space] diff --git a/vector_addition_system b/vector_addition_system @@ -13,12 +13,16 @@ Generalizations: - [vector_addition_system_pushdown] - [vector_addition_system_nested] -Complexity of the [reachability] problem: [ackermann_function] +Complexity of the [VASS_reachability] problem: [ackermann_function] - https://www.quantamagazine.org/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204/ -- apparently still open when [dimension] is constant +- known to be [ackermann_complete] +- the reachable sets are [almost_semi_linear] +- complexity apparently still open when [dimension] is constant two-dimensional VAS with one test on counters, like [counter_automata]: [leroux2020reachability] +They correspond to [Minsky_machines] but without zero tests + Restrictions: - [1_VASS], with only one counter @@ -27,3 +31,5 @@ Restrictions: Up: [automata] See also: [counter_automata] + +Aliases: vector addition systems, VAS, VASes, VASS, VASSes