commit 4b07a238c0e205d97147ace29b04da6415e9a5d7 parent 2d35b714ff2edefe2a1d4e6d3d401d4cb8b0145a Author: Antoine Amarilli <a3nm@a3nm.net> Date: Fri, 27 Jun 2025 12:06:50 +0200 commit with codex Diffstat:
64 files changed, 470 insertions(+), 21 deletions(-)
diff --git a/advice b/advice @@ -0,0 +1,9 @@ +# Advice + +Adding [nonuniform] input + +- [p_poly] corresponds to [ptime] +- [l_poly] corresponds to [logspace] +- [ll_polylog] corresponds to [llogspace] + +Up: [complexity_class] diff --git a/antichain b/antichain @@ -0,0 +1,5 @@ +# Antichain + +In a [poset], an *antichain* is a subset of elements that are pairwise [incomparable] + +Up: [partial_order] diff --git a/automata_nondeterministic_dense b/automata_nondeterministic_dense @@ -0,0 +1,7 @@ +# Automata nondeterministic dense + +An [NFA] where the number of [transitions] is Theta(n^2) where n is the number of [states] + +Up: [automata_nondeterministic], [dense_graph] + +Aliases: dense NFA diff --git a/boolean_matrix_multiplication b/boolean_matrix_multiplication @@ -1,5 +1,7 @@ # BMM +The [computational_problem] of [matrix_multiplication] for the [boolean_semiring] + [boolean_matrix_multiplication_hypothesis] Variants: diff --git a/boolean_network b/boolean_network @@ -0,0 +1,5 @@ +# Boolean network + +https://en.wikipedia.org/wiki/Boolean_network + +Up: [cycluit] diff --git a/boundedness b/boundedness @@ -0,0 +1,10 @@ +# Boundedness + +The [computational_problem], given a [query] in a [recursive_query] formalism, to determine if it is [query_equivalent] to a [query_nonrecursive] + +- [datalog_boundedness] +- [CRPQ_boundedness] +- [UCRPQ_boundedness] +- [UC2RPQ_boundedness] + +Up: [database_theory_problem] diff --git a/cayley_table b/cayley_table @@ -0,0 +1,7 @@ +# Cayley table + +multiplication table of a [group] + +[evra2023verifying]: can verify in [linear_time] whether an input table is the multiplication table of a group + +Up: [group] diff --git a/co_lexicographic_order b/co_lexicographic_order @@ -0,0 +1,7 @@ +# Co lexicographic order + +defined in [cotumaccio2023colexicographically] + +See also: [lexicographic_order], [cotumaccio2024myhill] + +Up: [order] diff --git a/computational_problem_words b/computational_problem_words @@ -0,0 +1,12 @@ +# Computational problems on words + +- [shortest_common_superstring] +- [longest_common_substring] +- [shortest_common_supersequence] +- [longest_common_subsequence] + +Up: [computational_problem], [words] + +See also: [formal_language_computational_problem] + +Aliases: Computational problems on words diff --git a/connectivity_circuit b/connectivity_circuit @@ -0,0 +1,6 @@ +# Connectivity circuit + +Bounds on [monotone_circuits] for [connectivity]: cf [karchmer1988monotone] +- also gives bounds on [monotone_formulas] + +Up: [connectivity] diff --git a/context_free_grammar_deterministic b/context_free_grammar_deterministic @@ -0,0 +1,9 @@ +# Deterministic Context free grammar + +[CFG] accepted by [pushdown_automaton_deterministic] + +no good intrinsic formulation in terms of [CFGs] + +Up: [context_free_grammar], [determinism] + +Aliases: DCFG, DCFGs diff --git a/cycle_problem b/cycle_problem @@ -0,0 +1,9 @@ +# Cycle problem + +The [computational_problem] of finding a [cycle] in a [graph] + +[yuster1997finding] for [cycle_even] + +See also: [clique_problem] + +Up: [graph_problem], [cycle] diff --git a/database_theory_problem b/database_theory_problem @@ -0,0 +1,15 @@ +# Database theory problem + +- [boundedness] +- [query_evaluation] +- [query_containment_problem] +- [query_equivalence_problem] +- [query_determinacy_problem] +- [deletion_propagation] +- [query_resilience] +- [smallest_witness] +- [synthetic_witness] +- [pqe] +- [uniform_reliability] + +Up: [database_theory], [computational_problem] diff --git a/datalog_boundedness b/datalog_boundedness @@ -0,0 +1,11 @@ +# Datalog boundedness + +The [boundedness] problem for [Datalog] + +- [undecidable] for general [Datalog] +- [decidable] for: + - [datalog_guarded] + - [datalog_frontier_guarded] + - [datalog_monadic] + +Up: [boundedness] for [datalog] diff --git a/datalog_query_evaluation b/datalog_query_evaluation @@ -22,3 +22,5 @@ An important idea is to run the [CQs] of the [rule_bodies] efficiently: [conjunc Up: [datalog], [query_evaluation] See also: [query_optimization] + +Aliases: datalog evaluation diff --git a/dd b/dd @@ -0,0 +1,8 @@ +# d-Ds + +- mentioned in [monet2020solving] +- [open_problems]: + - [dd_lower_bounds] + - [dd_enumeration] + +Up: [d], [knowledge_compilation] diff --git a/dp b/dp @@ -0,0 +1,14 @@ +# DP class + +https://complexityzoo.net/Complexity_Zoo:D#dp + +second level of the [boolean_hierarchy] + +- [intersection] of a [NP] language and [coNP] language +- different from [np_cap_conp] + +defined in [papadimitriou1984complexity] + +Up: [boolean_hierarchy] + +See also: [dp_complete] diff --git a/enumeration_memory b/enumeration_memory @@ -0,0 +1,7 @@ +# Enumeration memory + +The [space_complexity] of [enumeration] [algorithms], usually during the [enumeration_phase] + +- [enumeration_constant_memory] + +Up: [enumeration_definition] diff --git a/expressiveness b/expressiveness @@ -0,0 +1,8 @@ +# Expressiveness + +- [datalog_expressiveness] +- [spanner_expressiveness] +- [dependency_expressiveness] +- [neural_network_expressiveness] + +Up: [logic] diff --git a/factorial_language b/factorial_language @@ -0,0 +1,9 @@ +# Factorial language + +A [formal_language] L which is [language_closed] under [factor], i.e., any [factor] of a [word] of L is also in L + +Cf [deluca1990some] + +Up: [factor] + +See also: [ideal] diff --git a/formal_language_computational_problems b/formal_language_computational_problems @@ -13,3 +13,5 @@ Up: [formal_language] Aliases: formal language computational problem + +See also: [Computational_problems_on_words] diff --git a/fourier_transform b/fourier_transform @@ -0,0 +1,5 @@ +# Fourier transform + +- [fast_fourier_transform] + +Up: [mathematics] diff --git a/hypergraph_learning b/hypergraph_learning @@ -0,0 +1,5 @@ +# Hypergraph learning + +on [random_hypergraph]: [austhof2025nonadaptive] + +Up: [graph_learning] diff --git a/hypertree_width_variants b/hypertree_width_variants @@ -0,0 +1,8 @@ +# Hypertree width variants + +- [generalized_hypertree_width], with [edge_cover] +- [hypertree_width] (and [hypertree_decomposition]) with [special_condition] on the projected variables + - makes [tree_decomposition_computation] easier +- [query_decomposition] + +Up: [width_measure] for [hypergraph] diff --git a/knapsack b/knapsack @@ -0,0 +1,17 @@ +# Knapsack problem + +We have items with weights and values, we want to find the best total value possible while keeping the weight under a certain limit + +It is [np_complete] but not [strongly_np_complete] as there is a [pseudo_polynomial_time] algorithm. + +There is an [fptas] + +Special cases: +- [subset_sum] +- [change_making_problem] + +Generalizations: [integer_linear_programming] + +Up: [decision_problem], [optimization_problem] + +See also: [bin_packing] diff --git a/language_directed b/language_directed @@ -0,0 +1,12 @@ +# Directed language + +[formal_language] where for any two words u, v of the language, there is w in the language such that u and v are both [subwords] of w + +- makes it easier to check if two languages have the same [downwards_closure] +- makes it easier to check [language_equivalence] + +the [downward_closure] of a directed language is a single [language_ideal] + +Up: [ganardi2024directed] + +Aliases: directed language, directed languages diff --git a/language_equivalence b/language_equivalence @@ -12,4 +12,4 @@ Up: [formal_language_computational_problem], [equivalence] See also: [query_equivalence], [language_inclusion], [regular_expression_equivalence], [automaton_equivalence] -Aliases: language equivalent +Aliases: language equivalent, language equivalence problem diff --git a/logic_atom b/logic_atom @@ -0,0 +1,8 @@ +# Logic atom + +"Atom book" de [bojanczyk]: https://www.mimuw.edu.pl/~bojan/paper/atom-book +[bojanczyk2019slightly] + +Up: [atom] + +See also: [xpath] diff --git a/longest_common_extension b/longest_common_extension @@ -1,13 +0,0 @@ -# Longest common extension - -Uses [suffix_array] - -Related open problem: [mirror_lce] - -Generalization: [longest_common_extension_wildcards] - -Up: [stringology] - -See also: [longest_common_subsequence] - -Aliases: LCE diff --git a/longest_common_substring b/longest_common_substring @@ -1,7 +1,11 @@ # Longest common substring -linear time with [suffix_tree] +Given two [words] u and v, find a [word] w of maximal [length] such that w is a [factor] of u and of v + +Can be solved in [linear_time] with a [suffix_tree] Up: [stringology], [subword] See also: [longest_common_subsequence] + +Aliases: longest common factor, longest common infix diff --git a/menage_problem b/menage_problem @@ -0,0 +1,9 @@ +# Menage problem + +https://en.m.wikipedia.org/wiki/M%C3%A9nage_problem + +Seating male-and-female couples at a table so that men and women alternate and no one sits next to their partner + +Up: [combinatorics] + +See also: [heteronormative_math] diff --git a/monet2020solving b/monet2020solving @@ -0,0 +1,6 @@ +# Monet2020solving + +- [hasse_diagram] of the [hk_queries], where only the bottom element is a zero of the [mobius_function] +- [q9] query + +Up: [academic_paper], [pqe] diff --git a/nae3sat b/nae3sat @@ -0,0 +1,5 @@ +# NAE3SAT + +https://en.wikipedia.org/wiki/Not-all-equal_3-satisfiability + +Up: [sat_variants] diff --git a/nllogspace b/nllogspace @@ -0,0 +1,9 @@ +# NLL + +Like [nlogspace] but with [log_log] + +Mentioned in [kapoutsis2014two] + +Up: [nlogspace] + +See also: [llogspace] diff --git a/optimized_naive_evaluation b/optimized_naive_evaluation @@ -0,0 +1,5 @@ +# Optimized naive evaluation + +In [bourgaux2022revisiting]: [naive_evaluation] but we stop when deriving the goal atom, i.e., we only consider [derivation_tree_datalog] of minimal [height] + +Up: [datalog_evaluation] diff --git a/other_side b/other_side @@ -0,0 +1,9 @@ +# Other side + +the [duality] between [constraint_satisfaction_problem] and [query_evaluation_conjunctive_query] + +- [grohe2007complexity] about [constraint_satisfaction_problem] +- [dalmau2004complexity] about [homomorphism_counting] +- [bulatov2020approximate] about [counting_csp_approximate] + +Up: [counting_csp] diff --git a/pattern_language_equivalence b/pattern_language_equivalence @@ -0,0 +1,11 @@ +# Pattern language equivalence + +[nowotka2024equivalence]: decidable for [non-erasing_substitutions] + +[open_problem] whether it is [decidable] for [erasing_substitutions] + +[NP_complete] for [erasing_substitutions] with [patterns_with_variables_terminal_free] [nowotka2024equivalence] + +[undecidability] if allowing [regular_language] constraints on variables, cf [nowotka2024equivalence] + +Up: [language_equivalence_problem], [pattern_language] diff --git a/pattern_matching_practice b/pattern_matching_practice @@ -0,0 +1,7 @@ +# Pattern matching practice + +- https://smart-tool.github.io/smart/ +- [strstr] + - uses [two_way_string_matching_algorithm]? + +Up: [pattern_matching], [practice] diff --git a/planar_language b/planar_language @@ -0,0 +1,15 @@ +# Planar language + +A [regular_language] accepted by a [planar_automaton] + +[book1976inherently]: +- every [regular_language] has a nondeterministic [planar_automaton] +- some [regular_languages] do not have deterministic [planar_automata] +- [bonfante2022genus]: [genus] forms a strict hierarchy +- still not known whether it is computable or what is the characterization + +Other notion: [nguyen2023two] + +Also: https://cstheory.stackexchange.com/questions/47427/planarity-of-planar-finite-automata-intersection + +Up: [planar_graph], [regular_language] diff --git a/primitive_word b/primitive_word @@ -7,3 +7,5 @@ A [word] which is not a [power_mathematics] of another [word] Up: [word] See also: [prime_number], [prime_number_decomposition], [primitive_word_conjecture] + +Aliases: primitive words diff --git a/probabilistic_databases_updates b/probabilistic_databases_updates @@ -0,0 +1,5 @@ +# Probabilistic databases under updates + +[berkholz2021probabilistic] + +Up: [pqe], [dynamic_data] diff --git a/provenance_lower_bound b/provenance_lower_bound @@ -0,0 +1,12 @@ +# Provenance lower bound + +Lower bounds on representations of query provenance + +- for [pqe_ucq]: [jha2012tractability] + - and lower bounds cited in [monet2020solving] for [decision_dnnf] and [dsdnnf] +- [amarilli2019connecting]: for [disjunctive_normal_form] / [conjunctive_normal_form] based on [treewidth] +- for [unboundedness]: [unboundedness_provenance] + +See also: [pqe] + +Up: [lower_bounds], [provenance_size] diff --git a/quantifier b/quantifier @@ -9,4 +9,4 @@ Up: [logic] See also: [QBF] -Aliases: quantification +Aliases: quantification, quantifiers diff --git a/query_containment_problem b/query_containment_problem @@ -5,7 +5,7 @@ - [CQ_containment_problem] for [CQs]: [NP_complete] - [UCQ_containment_problem] for [UCQs]: [NP_complete] -Up: [query_containment] +Up: [database_theory_problem], [query_containment] Aliases: QCP diff --git a/query_equivalence_problem b/query_equivalence_problem @@ -8,6 +8,6 @@ Always admits a [reduction] to the [query_containment_problem], because [query_e - [UCQ_equivalence_problem] for [UCQs]: [NP_complete] - [CRPQ_equivalence_problem] -Up: [decision_problem], [query_equivalence] +Up: [database_theory_problem], [query_equivalence] See also: [query_containment_problem], [bag_query_equivalence_problem] diff --git a/query_evaluation b/query_evaluation @@ -19,6 +19,6 @@ - [approximate_query_evaluation] - [query_approximation] -Up: [database_theory] +Up: [database_theory_problem] See also: [query_language], [enumeration_query_answers] diff --git a/regular_expression_deterministic b/regular_expression_deterministic @@ -37,3 +37,5 @@ subclass: [regular_expression_strongly_deterministic] [gelade2009regular] Up: [regular_expression], [determinism] Aliases: deterministic regular expression, deterministic regular expressions, one-unambiguous regular expression, one-unambiguous regular expressions, 1-unambgiuous regular expression, 1-unambiguous regular expressions + +See also: [Regular_language_union_free] diff --git a/regular_language_union_free b/regular_language_union_free @@ -8,6 +8,6 @@ The [regular_languages] whose definition as a [regular_expression] does not use Up: [regular_language_family] -See also: [union] +See also: [union], [disjunction_free] -Aliases: union free regular language, union free regular languages +Aliases: union free regular language, union free regular languages, regular expression union free, union free regular expression diff --git a/rpq_counting_answers b/rpq_counting_answers @@ -0,0 +1,8 @@ +# Rpq counting answers + +- [arenas2012counting] +- [losemann2012counting] + +Up: [counting_query_answers], [RPQ] + +See also: [rpq_query_evaluation] diff --git a/satisfiability_cnf b/satisfiability_cnf @@ -0,0 +1,9 @@ +# Satisfiability CNF + +The [satisfiability_boolean] problem on [CNFs] + +- [sat_variants] + +Up: [satisfiability_boolean], [conjunctive_normal_form] + +Aliases: CNF satisfiability, CNF SAT diff --git a/second_neighborhood_problem b/second_neighborhood_problem @@ -0,0 +1,5 @@ +# Second neighborhood problem + +https://en.wikipedia.org/wiki/Second_neighborhood_problem + +Up: [conjecture] on [graph_oriented] diff --git a/semantic_treewidth_evaluation b/semantic_treewidth_evaluation @@ -0,0 +1,8 @@ +# Semantic treewidth evaluation + +The [computational_problem] of [query_evaluation] for [queries] of small [semantic_treewidth] +- [FPT] with doubly exponential parameter in [morvan2025homomorphism] +- [FPT] with singly exponential parameter in [feier2024evaluating] + - cites [figueira2023approximation] + +Up: [semantic_treewidth], [query_evaluation] diff --git a/semiring_commutative b/semiring_commutative @@ -0,0 +1,7 @@ +# Semiring commutative + +A [semiring] where [product] is [commutative] + +Up: [semiring], [commutative] + +See also: [monoid_commutative] diff --git a/semiring_with_monus b/semiring_with_monus @@ -0,0 +1,7 @@ +# Semiring with monus + +A [semiring] that has a [monus] + +Up: [semiring] + +Aliases: M semiring diff --git a/shapley_value_omqa b/shapley_value_omqa @@ -0,0 +1,5 @@ +# Shapley value OMQA + +[bienvenu2024shapley] + +Up: [shapley_value], [omqa] diff --git a/shortest_common_supersequence b/shortest_common_supersequence @@ -0,0 +1,9 @@ +# Shortest common supersequence + +https://en.wikipedia.org/wiki/Shortest_common_supersequence + +Given two [words] u and v, find a [word] w of minimal [length] such that w is a [supersequence] of u and of v + +See also: [longest_common_subsequence], [shortest_common_non_subsequence], [shortest_common_superstring] + +Up: [computational_problem] on [words] diff --git a/shortest_common_superstring b/shortest_common_superstring @@ -0,0 +1,18 @@ +# Shortest common superstring + +https://en.wikipedia.org/wiki/Shortest_common_supersequence#Shortest_common_superstring + +Given a set of [words] S, find the shortest [word] containing all words of S as a [factor] + +- [turner1989approximation] +- [gallant1980finding]: + - bounds depending on the length of the input strings + - tractability when all input strings have length 2 (on an unbounded alphabet) + - [NP_hard] even when all strings are [primitive_words] and of length 3 (on an unbounded alphabet) +- [bliznets2015parameterized] + +Can be solved for two strings with [KMP], to know the longest [suffix] of a string which is a [prefix] of the other + +See also: [shortest_common_supersequence], [longest_common_substring] + +Up: [computational_problem] on [words] diff --git a/single_source_shortest_path_faster b/single_source_shortest_path_faster @@ -0,0 +1,13 @@ +# Single source shortest path faster + +Solve [single_source_shortest_path] faster than [bellman_ford] + +- variant: "scaling-based algorithms": O(m sqrt(n) log W) +- [bernstein2022negative] best paper: O(m log^8 n log W) + - [bringmann2023negative] improved by [log_shaving] +- open whether log W can be removed + +recent result [bernstein2023negative] improving [bellman_ford] +vs [lower_bounds] on [circuit_classes] for this problem [jukna2016optimality] + +Up: [single_source_shortest_path_algorithm] diff --git a/spanner_expressiveness b/spanner_expressiveness @@ -0,0 +1,11 @@ +# Spanner expressiveness + +- [regex_formulas] are strict subset of [variable_set_automata] (hierarchical) +- when adding [relational_algebra]: + - they become equal + - for automata, adding [relational_algebra] makes no difference +- adding [string_equality]: [freydenberger2016document] + +Up: [spanner], [expressiveness] + +See also: [core_spanner] diff --git a/square b/square @@ -0,0 +1,7 @@ +# Square + +- [squares_in_squares] + +Up: [geometry] + +See also: [squaring] diff --git a/subhypergraph b/subhypergraph @@ -0,0 +1,8 @@ +# Subhypergraph + +The generalization of [subgraphs] to [hypergraphs]: remove some [hyperedges] +- and possibly remove some [isolated_vertices] + +Up: [hypergraph], [subgraph] + +Aliases: subhypergraphs diff --git a/treelike_data b/treelike_data @@ -0,0 +1,7 @@ +# Treelike data + +Data which is [treelike], i.e., of bounded [treewidth] + +On such data we can do [pqe_mso] + +Up: [data] of bounded [treewidth], [types_of_data] diff --git a/weak_exponential_time_hypothesis b/weak_exponential_time_hypothesis @@ -0,0 +1,9 @@ +# Weak exponential time hypothesis + +The [computational_hypothesis] that we cannot solve [3-SAT] in time 2^{o(n)} + +Implied by [exponential_time_hypothesis] but not equivalent +- cf https://en.wikipedia.org/wiki/Exponential_time_hypothesis +- indeed you could have algorithms in 2^{delta n} for every delta > 0, that get more and more complicated, and none for delta = 0 + +Up: [exponential_time_hypothesis] diff --git a/zigzag_graph b/zigzag_graph @@ -0,0 +1,11 @@ +# Zigzag graph + +Defined in [morvan2025homomorphism] Example VIII.2.11 + +They form an infinite family of [critical_obstructions] for the [2_path] + +Up: [graph_family] + +Aliases: zigzag graphs + +See also: [Critical_obstruction]