commit 145294cdd6f928e8526d592993dec838622866ca parent 208ed427e4ca46955da5f45dd65fe28a4dd630a5 Author: Antoine Amarilli <a3nm@a3nm.net> Date: Thu, 26 Jun 2025 23:21:55 +0200 commit with codex Diffstat:
54 files changed, 408 insertions(+), 8 deletions(-)
diff --git a/2_regular b/2_regular @@ -3,3 +3,5 @@ A 2-regular graph is a [disjoint_union] of [cycles] Up: [graph_regular] + +See also: [degree_2_graph] diff --git a/3sat_3_occurrences b/3sat_3_occurrences @@ -0,0 +1,12 @@ +# 3SAT 3 occurrences + +[3SAT] where each variable occurs at most 3 times: + +- do you have exactly 3 literals per clause, or at most 3 literals per clause? + - if 3 literals per clause: + - [3SAT_3_occurrences_exactly3] ([PTIME]) + - note: if you go beyond [3SAT] and allow larger clauses, then it is still [NP_complete]: cf [tovey1984simplified] + - if at most 3 literals per clause: + - [3SAT_3_occurrences_atmost3] + +Up: [3sat_variants] diff --git a/3sat_3_occurrences_atmost3 b/3sat_3_occurrences_atmost3 @@ -0,0 +1,10 @@ +# 3SAT 3 occurrences atmost3 + +[3SAT] with at most 3 occurrences of each variable and some clauses may have size <3 + +- [3SAT] with 2 or 3 literals by clause and at most 3 occurrences of each variable is [np_hard] + - https://cs.stackexchange.com/questions/48442/3-sat-for-variables-appearing-3-times +- [3SAT] with <= 3 literals by clause and each variable occurs 1 time positively and 2 times negatively is [np_hard] + - Lemma 1 of [yannakakis1981edge] + +Up: [3sat_3_occurrences] diff --git a/3sat_3_occurrences_exactly3 b/3sat_3_occurrences_exactly3 @@ -0,0 +1,10 @@ +# 3SAT 3 occurrences exactly3 + +[3SAT] with each clause having size exactly 3 and at most 3 occurrences of each variable + +- 3-SAT with exactly 3 literals par clause and exactly 3 occurrences of each variable is always satisfiable by [halls_theorem] +- so the same extends if you have exactly 3 literals per clause and at most 3 occurrences per variable, as you can complete the smaller clauses to clauses of size 3 + +Does not generalize if clauses can have size <3, cf [3SAT_3_occurrences_atmost3] + +Up: [3sat_3_occurrences] diff --git a/4clique_hypothesis b/4clique_hypothesis @@ -0,0 +1,7 @@ +# 4clique hypothesis + +[bringmann2022tight]: you cannot determine in O(n^3) whether a [graph] contains a [4_clique] + +Up: [computational_hypothesis], [4_clique] + +See also: [hyperclique_hypothesis] diff --git a/algorithms_techniques b/algorithms_techniques @@ -0,0 +1,7 @@ +# Algorithms techniques + +- [color_coding], cf [k_path] +- [four_russians_trick] +- [tabulation] + +Up: [algorithms] diff --git a/bifix_free_language b/bifix_free_language @@ -0,0 +1,7 @@ +# Bifix free language + +A [formal_language] which is both [prefix_free] and [suffix_free] + +See also: [factor_closed_language] + +Up: [formal_language] diff --git a/bipartite_regular_graph b/bipartite_regular_graph @@ -0,0 +1,10 @@ +# Bipartite regular graph + +https://mathoverflow.net/questions/428212/perfect-matching-decomposition-algorithm-for-bipartite-regular-graphs +- a [bipartite_graph] can be decomposed into edge-disjoint [perfect_matchings] iff the [graph] is regular +- uses [Hall's_theorem], specifically [regular_bipartite_graph_perfect_matching] + - https://math.stackexchange.com/questions/4361540/if-g-is-n-regular-then-g-has-n-disjoint-perfect-matchings + +Up: [graph_regular], [bipartite_graph] + +Aliases: regular bipartite graph diff --git a/boolean_function_classes b/boolean_function_classes @@ -0,0 +1,10 @@ +# Boolean function classes + +- [boolean_function_monotone] +- [positive_threshold_function] +- [boolean_function_regular] +- [boolean_function_evasive] + +Up: [boolean_function] + +See also: [circuit_classes] diff --git a/boolean_function_regular b/boolean_function_regular @@ -0,0 +1,7 @@ +# Boolean function regular + +cf https://cstheory.stackexchange.com/questions/31469/which-monotone-boolean-functions-are-representable-as-thresholds-on-sums + +Up: [boolean_function_classes] + +Aliases: regular Boolean function, regular Boolean functions diff --git a/comparison_sort b/comparison_sort @@ -0,0 +1,19 @@ +# Comparison sort + +## [algorithms] + +- [insertion_sort] +- [selection_sort] +- [heap_sort] +- [binary_tree_sort] +- [quicksort] +- [merge_sort] +- [bubble_sort] +- [bogosort] + +## Other + +- [comparison_sort_lower_bound] +- [comparison_sort_number] + +Up: [sorting], [comparison] diff --git a/comparison_sort_number b/comparison_sort_number @@ -0,0 +1,9 @@ +# Comparison sort number + +The number of [comparisons] needed to sort n elements + +Studied in [stober2022lower] + +Up: [comparison_sort] + +See also: [decision_tree], [gods_algorithm], [addition_chain] diff --git a/conjunctive_query_inequality b/conjunctive_query_inequality @@ -8,4 +8,4 @@ Up: [conjunctive_query], [query_inequality] See also: [query_with_negation] -Aliases: CQ inequalities, conjunctive query inequalities +Aliases: CQ inequalities, conjunctive query inequalities, CQs with inequalities, CQ with inequalities diff --git a/context_free_language_reachability b/context_free_language_reachability @@ -0,0 +1,9 @@ +# Context free language reachability + +Given a [directed_graph] G with [edges] labeled with [letters] from an [alphabet], a [source] s and [sink] t, and a [CFG] Gamma, define if there is a [walk] from s to t spelling a word of Gamma. + +Can be solved in [cubic] time [bringmann2024nfa] + +[Subcubic_equivalent] to [2NPDA_acceptance] + +Up: [computational_problem], [graph], [CFGs] diff --git a/conversion b/conversion @@ -11,3 +11,5 @@ Up: [knowledge_compilation] See also: [amarilli2019connecting] + +Aliases: converting diff --git a/conversion_circuit b/conversion_circuit @@ -0,0 +1,19 @@ +# Conversion circuit + +The [function_problem] of [converting] a [circuit] from a [circuit_class] to another + +- [cnf_to_dnnf] +- [cnf_to_decision_dnnf] + +in [amarilli2019connecting]: +- [dnnf_to_nfbdd] ([quasipolynomial]) +- [ddnnf_to_ufbdd] +- [decison_dnnf_to_fbdd] +- other cases + +- [obdd_to_boolean_formula] +- [boolean_circuit_to_nbdd] + +Up: [conversion] + +See also: [darwiche2002knowledge], [circuit_circus] diff --git a/decision_sdnnf b/decision_sdnnf @@ -0,0 +1,5 @@ +# Decision-SDNNF + +A [decision_dnnf] which is a [structured_circuit] + +Up: [decision_dnnf], [sdnnf] diff --git a/degree_of_ambiguity b/degree_of_ambiguity @@ -13,4 +13,4 @@ By regime: Up: [nondeterministic] -See also: [density_function], [k_ambiguous_ddnnf] +See also: [density_function], [k_ambiguous_ddnnf], [FewP] diff --git a/disruptive_trio b/disruptive_trio @@ -0,0 +1,11 @@ +# Disruptive trio + +Condition to show the intractability of [direct_access] for [CQs] with results ordered in [lexicographic_order], introduced in [carmeli2021tractable] + +three [variables] x y z such that: +- x > z and y > z in the specification of the [lexicographic_order] +- x and z cooccur in an [atom], y and z cooccur in an [atom], x and y do not cooccur in an [atom] + +[disruptive_trio_fhw] + +Up: [carmeli2021tractable] diff --git a/distance_product b/distance_product @@ -0,0 +1,13 @@ +# Distance product + +Given two [adjacency_matrices] A and B their *distance product* is +(A*B)[i,j ] defined to be min_k (A[i,k ] + B[k,j ]) +- this is [matrix_multiplication] in the [tropical_semiring] + +[APSP_reduces_to_distance_product] + +Computing the distance product reduces to [negative_triangle] + +See also: [all_pairs_shortest_path] + +Aliases: min plus product, min-plus product diff --git a/embedding b/embedding @@ -3,3 +3,5 @@ An [injective] [homomorphism] Up: [homomorphism], [injective] + +See also: [subsequence_embedding] diff --git a/fewp b/fewp @@ -0,0 +1,12 @@ +# FewP + +https://complexityzoo.net/Complexity_Zoo:F#fewp + +[Complexity_class] of [decision_problems] such that: + +- on negative instances, all [runs] are rejecting +- on positive instances, there is an [accepting_run], and the number of [accepting_runs] is bounded by a [polynomial] as a function of the input + +Up: [UP], [complexity_class] + +See also: [polynomial_ambiguity], [Degree_of_ambiguity] diff --git a/graph_regular b/graph_regular @@ -2,9 +2,7 @@ A [graph] where all [vertices] have the same [degree] -https://mathoverflow.net/questions/428212/perfect-matching-decomposition-algorithm-for-bipartite-regular-graphs -- a [bipartite_graph] can be decomposed into edge-disjoint [perfect_matchings] iff the [graph] is regular -- uses [halls_theorem] https://math.stackexchange.com/questions/4361540/if-g-is-n-regular-then-g-has-n-disjoint-perfect-matchings +[bipartite_regular_graph] [Special_case]: - [2_regular] diff --git a/halls_theorem b/halls_theorem @@ -0,0 +1,15 @@ +# Hall's theorem + +In a [bipartite_graph] (X, Y), there is a [matching] incident to each [vertex] of X iff for each [subset] W of X, we have |W| \leq |Neighbors(W)|. + +[Hall's_theorem_proof] + +Consequence: [regular_bipartite_graph_perfect_matching] + +Consequence for [satisfiability_boolean]: [3sat_3_occurrences_exactly3], but contrast [3sat_3_occurrences_atmost3] + +Extension to [hypergraphs]: +- https://en.wikipedia.org/wiki/Hall-type_theorems_for_hypergraphs#Haxell's_condition:_smallest_transversal +- cf [transversal] + +Up: [graph] diff --git a/incremental_maintenance_datalog b/incremental_maintenance_datalog @@ -0,0 +1,5 @@ +# Incremental maintenance datalog + +- [xu2023zodiacedge] + +Up: [incremental_maintenance], [datalog] diff --git a/inequality_mathematics b/inequality_mathematics @@ -3,7 +3,7 @@ - [conjunctive_query_inequality] - [enumeration_inequality] -See also: [concentration_inequality], [partial_order], [inequation], [disequality], [equality] +See also: [concentration_inequality], [partial_order], [inequation], [disequality], [equality], [comparison] Up: [mathematics] diff --git a/interval_graph b/interval_graph @@ -0,0 +1,6 @@ +# Interval graph + +- [proper_interval_graph] +- [unit_interval_graph] + +Up: [graph_family], [interval] diff --git a/k_ambiguous_automaton b/k_ambiguous_automaton @@ -0,0 +1,5 @@ +# K ambiguous automaton + +- [word_automaton_k_unambiguous] + +Up: [k_unambiguous] diff --git a/k_unambiguous b/k_unambiguous @@ -0,0 +1,9 @@ +# K unambiguous + +- [k_ambiguous_ddnnf] +- [k_ambiguous_automaton] +- [context_free_grammar_k_ambiguous] + +Up: [unambiguous] + +See also: [Degree_of_ambiguity] diff --git a/linear_relaxation b/linear_relaxation @@ -0,0 +1,5 @@ +# Linear relaxation + +Taking an [integer_linear_program] or [mixed_integer_linear_program] and transforming it to a [linear_program] by dropping the constraint that the [variables] (or some [variables]) must be [integers] + +Up: [integer_linear_programming] diff --git a/message_passing b/message_passing @@ -0,0 +1,7 @@ +# Message passing + +[Algorithm] used for [probabilistic_inference], in conjunction with [treewidth] + +[message_passing_aggregation] + +Up: [algorithm], [probabilistic_inference] diff --git a/nfa_acceptance b/nfa_acceptance @@ -0,0 +1,11 @@ +# NFA acceptance + +The [automaton_acceptance] problem for an [NFA] + +Can be solved by [state_set_simulation] + +[Hardness_hypothesis] that this is optimal in [backurs2016which], see also [bringmann2024nfa] + +Up: [automaton_acceptance], [NFA] + +See also: [nfa_unary_lengths] diff --git a/partial_automaton b/partial_automaton @@ -0,0 +1,7 @@ +# Partial automaton + +An [automaton] without the [initial_states] or [final_states] specified + +Up: [automata] + +Aliases: semiautomaton, semiautomata, partial automata diff --git a/permutation_automaton b/permutation_automaton @@ -0,0 +1,7 @@ +# Permutation automaton + +https://en.wikipedia.org/wiki/Permutation_automaton + +See also: [language_group] + +Up: [automata], [permutation] diff --git a/provenance_membership_testing b/provenance_membership_testing @@ -0,0 +1,18 @@ +# Provenance membership testing + +Studied in [calautti2023complexity], for [Datalog] + +- Fix a [query] Q +- Input: + - A [database] D + - Optionally: A [query_answer] t + - A subdatabase D' of D +- Output: Decide if D' is in the provenance (optionally: of t) of Q on D. + +This is [provenance_operational] not [provenance_definitional], so for instance in [Datalog] it depends on the set of [proof_trees] + +Results in [calautti2023complexity]: + +Also: [calautti2024complexity] on computing minimal sets, and also testing when the multiplicity is given as input + +Up: [provenance_datalog] diff --git a/pseudorandomness b/pseudorandomness @@ -0,0 +1,5 @@ +# Pseudorandomness + +- [prng] + +Up: [randomness] diff --git a/redos_counting b/redos_counting @@ -0,0 +1,5 @@ +# Redos for regexps with counting + +[turonova2022counting] + +Up: [REDOS], [regular_expression_counting_complexity] diff --git a/regular_bipartite_graph_perfect_matching b/regular_bipartite_graph_perfect_matching @@ -0,0 +1,7 @@ +# Regular bipartite graph perfect matching + +A [corollary] of [Hall's_theorem]: every [bipartite_regular_graph] has a [perfect_matching] + +[regular_bipartite_graph_perfect_matching_proof] + +Up: [halls_theorem], [bipartite_regular_graph], [perfect_matching] diff --git a/regular_language_list b/regular_language_list @@ -0,0 +1,5 @@ +# List of regular languages + +- [parity_language] + +Up: [regular_language] diff --git a/relation b/relation @@ -0,0 +1,6 @@ +# Relation + +- [equivalence_relation] +- [word_relation] + +Up: [mathematics] diff --git a/rpq_captures b/rpq_captures @@ -0,0 +1,7 @@ +# RPQ captures + +Extending [RPQs] with [capture_variable] + +[academic_paper]: [schmid2022conjunctive] + +Up: [regular_path_query], [refl_spanner] diff --git a/simple_path_problem b/simple_path_problem @@ -0,0 +1,9 @@ +# Simple path problem + +[Computational_problem] of deciding if there is a [simple_path] in a [graph] from a vertex s to a vertex t + +Obviously [PTIME] by computing a [shortest_path] + +- [simple_path_rpq_problem] + +Up: [computational_problem], [simple_path] diff --git a/simple_path_rpq_problem b/simple_path_rpq_problem @@ -1,6 +1,6 @@ # Simple path rpq problem -Decide if there is a [simple_path] satisfing a [RPQ] +Decide if there is a [simple_path] satisfing a [RPQ] from a vertex s to a vertex t in a [graph] Topic of the [simple_path_trichotomy] diff --git a/solver b/solver @@ -0,0 +1,9 @@ +# Solver + +- [sat_solver] +- [cp_solver] +- [ilp_solver] +- [smt_solver] +- [mip_solver] + +Up: [software] diff --git a/spanner_parallelizability b/spanner_parallelizability @@ -0,0 +1,5 @@ +# Spanner parallelizability + +[doleschal2019annotated] (with delimiters) + +Up: [spanner] diff --git a/state_set_simulation b/state_set_simulation @@ -0,0 +1,15 @@ +# State set simulation + +[Algorithm] to test if a [word] is accepted by [automaton_epsilon_transitions] + +complexity O(nm) time and O(m) space + +Already mentioned in [thompson1968regular], cf [thompsons_automaton] + +accelerate it: [state_set_simulation_faster] + +Lower bounds from [backurs2016which] + +See also: [regular_expression_matching] + +Up: [automaton_acceptance] diff --git a/state_set_simulation_tabulation b/state_set_simulation_tabulation @@ -0,0 +1,13 @@ +# State set simulation tabulation + +Doing [state_set_simulation_faster] on a [TNFA] which is small relative to the word size + +- Encode state-set as bit string + - to read a letter, do "[shift_and] technique" [bit_tricks] + - to move forward with [epsilon_edges], do [universal_tabulation] for each possible [TNFA] + +you get complexity O(nm/log n) with n the [word] size and m the [regular_expression] size + +cf [bille2008faster] + +Up: [state_set_simulation_faster] diff --git a/strongly_np_complete b/strongly_np_complete @@ -1,6 +1,6 @@ # Strong NP-completeness -[np_complete] even when the input is represented in unary +The fact of being [NP_complete] even numbers in the input are represented in unary [strongly_np_complete_list] diff --git a/strongly_np_complete_list b/strongly_np_complete_list @@ -0,0 +1,8 @@ +# Strongly NP complete list + +List of [strongly_np_complete] [decision_problems]: + +- [3_partition] +- [bin_packing] + +Up: [strongly_np_complete] diff --git a/structuredness b/structuredness @@ -0,0 +1,9 @@ +# Structuredness + +A [Boolean_circuit] in [DNNF] that has a [vtree] + +- [circuit_restructuring] + +Up: [circuit_condition] + +Aliases: structured circuit, structured, structured circuits diff --git a/subsequence_embedding b/subsequence_embedding @@ -0,0 +1,5 @@ +# Subsequence embedding + +The *embedding* of a [word] u as a [subsequence] of [word] v is the [increasing] function mapping each position of u to the corresponding position of v (which must contain the same letter) + +Up: [subsequence], [embedding] diff --git a/unambiguous_marked_product b/unambiguous_marked_product @@ -5,3 +5,5 @@ A [marked_product] which is [unambiguity] in the sense that there is a unique de [unambiguous_language] formed of these Up: [marked_product], [unambiguity] + +Aliases: unambiguous marked products diff --git a/union_of_conjunctive_queries_inequality b/union_of_conjunctive_queries_inequality @@ -0,0 +1,7 @@ +# Union of conjunctive queries inequality + +A [disjunction] of [CQs_with_inequalities] + +Up: [UCQ], [query_inequality] + +Aliases: union of conjunctive query inequality diff --git a/vtree b/vtree @@ -0,0 +1,7 @@ +# Vtree + +A [tree] on the [variables] of a [circuit], used to define [structuredness] + +Up: [tree], [knowledge_compilation] + +See also: [variable_order]