commit a6c5be03e516ccfb9806911d2215c23902145dcb parent 81d9ee0b8dbaf4ae79f5b2af03ce0c289ded4f27 Author: Antoine Amarilli <a3nm@a3nm.net> Date: Tue, 28 Oct 2025 07:48:36 +0100 Merge remote-tracking branch 'origin/master' Diffstat:
42 files changed, 214 insertions(+), 30 deletions(-)
diff --git a/3sat_3_occurrences b/3sat_3_occurrences @@ -1,12 +0,0 @@ -# 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/acyclic_free_connex b/acyclic_free_connex @@ -9,3 +9,5 @@ When a query is not acyclic free-connex you can often reduce from [boolean_matri Up: [conjunctive_query_acyclic] See also: [enumeration_cqs] + +Aliases: Acyclic free connex CQ, acyclic free connex CQs diff --git a/automaton_equivalence b/automaton_equivalence @@ -1,7 +1,7 @@ # Automaton equivalence -- [pspace_complete] on [automata_nondeterministic] -- [ptime] on [automata_deterministic] via [product_construction] +- [NFA_equivalence]: [pspace_complete] +- [DFA_equivalence]: [ptime] via [product_construction] - [automaton_equivalence_pushdown_automaton] - [automaton_equivalence_pushdown_automaton_deterministic] diff --git a/automaton_inclusion b/automaton_inclusion @@ -1,8 +1,7 @@ # Automaton inclusion -[PSPACE_complete] for [nondeterministic_automata] - -[PTIME] for [automata_deterministic] +- [NFA_inclusion]: [PSPACE_complete] +- [DFA_inclusion]: [PTIME] via [product_construction] Up: [automata_problems], [language_inclusion] diff --git a/chinese_postman_problem b/chinese_postman_problem @@ -1,8 +1,10 @@ # Chinese postman problem +https://en.wikipedia.org/wiki/Chinese_postman_problem + The [computational_problem] of computing the shortest [path] or [circuit] that visits every [edge] of a [graph] at least once -Can be posed for [graph_directed] or [graph_undirected] +Can be posed for [graph_directed] or [graph_undirected]. It is [PTIME] in both cases [NP_complete] on: - [Undirected_graphs] when traversal cost is different per direction: [windy_postman_problem] diff --git a/conjunctive_query_acyclic b/conjunctive_query_acyclic @@ -25,4 +25,4 @@ See also: [fagin1983degrees], [guarded_fragment], [alpha_acyclic], [conjunctive_ Up: [conjunctive_query], [query_acyclic] -Aliases: acyclic conjunctive query, acyclic conjunctive queries, acyclic CQ, acyclic CQs, CQ acyclic, acyclic queries, acyclic query +Aliases: acyclic conjunctive query, acyclic conjunctive queries, acyclic CQ, acyclic CQs, CQ acyclic, acyclic queries, acyclic query, ACQ, ACQs diff --git a/context_free_grammar b/context_free_grammar @@ -54,6 +54,7 @@ ## Results - [Greibach's_theorem] +- [Chomsky-Schützenberger_theorem] See also: [regular_language], [chomsky_hierarchy], [context_free_language], [inherently_ambiguous], [graph_grammar], [semilinear_set], [language_power_series], [Hyperedge_replacement_grammar] diff --git a/cutwidth_directed b/cutwidth_directed @@ -1,5 +1,9 @@ -# Cutwidth directed +# Directed cutwidth introduced in [chudnowski2012tournament] +Not the same as the [cutwidth] of the [underlying_undirected_graph] of a [directed_graph] + Up: [cutwidth] on [directed_graphs] + +Aliases: directed cutwidth diff --git a/description_logics b/description_logics @@ -14,3 +14,5 @@ Topics: Up: [logic] See also: [FO2], [Guarded_Fragment] + +Aliases: description logic diff --git a/dfa_equivalence b/dfa_equivalence @@ -0,0 +1,7 @@ +# DFA equivalence + +[ptime] via [product_construction] + +Up: [automaton_equivalence] on [DFAs] + +See also: [DFA_inclusion], [NFA_equivalence] diff --git a/dfa_inclusion b/dfa_inclusion @@ -0,0 +1,7 @@ +# DFA inclusion + +in [PTIME] via [product_construction] + +Up: [automaton_inclusion] for [DFAs] + +See also: [DFA_equivalence], [NFA_inclusion] diff --git a/disjoint_path_2 b/disjoint_path_2 @@ -0,0 +1,15 @@ +# Two-disjoint path problem + +The [decision_problem], given a [directed_graph] and sources s1 and s2 and sinks t1 and t2, of determining whether there are vertex-disjoint [simple_paths] from s1 to t1 and s2 to t2 + +It is [NP_hard], cf [fortune1980directed] + +The "[simple_path] via node" problem is already [NP_hard] + +Not to be confused with the problem of finding two vertex-disjoint paths from {s1, s2} to {t1, t2}, which can be solved in [PTIME] using [network_flows]; in that case you cannot enforce which pairs of vertices are being connected by the two paths + +Up: [disjoint_paths] + +See also: [edge_connectedness], [simple_path_RPQ] + +Aliases: two disjoint path problem, two disjoint paths, Disjoint path 2, twodisjoint path problem, two disjoint simple path, two disjoint simple paths, two disjoint simple path problem, two disjoint simple paths problem diff --git a/disjoint_paths_undirected b/disjoint_paths_undirected @@ -13,3 +13,5 @@ Cf [liu2025disjoint] for a review and for a generalization to [modularity_constr Special case: [2_disjoint_paths_undirected] Up: [disjoint_paths] on [undirected_graphs] + +Aliases: undirected k disjoint paths, undirected k disjoint path problem diff --git a/exact_matching b/exact_matching @@ -5,4 +5,6 @@ [maalouly2022exact]: this is in [RP] and not known to be in [ptime] +Variant: [exact_matching_parity] + Up: [matching] diff --git a/exact_matching_parity b/exact_matching_parity @@ -0,0 +1,14 @@ +# Exact matching parity + +- in [bipartite_graphs], can decide in [PTIME] whether there is a [perfect_matching] with an even number of red edges + - proof in [datta2010perfect] + - generalization to [maximum_matching] + - https://cstheory.stackexchange.com/a/41357 + - unknown for other moduli? + - unknown for non-bipartite graphs? +- for general graphs and constant number of colors it can be done in [PTIME] + - [RP] algorithm from [mulmuley1987matching] + - cf [marx2004list] + - https://cstheory.stackexchange.com/a/41343 + +Up: [matching_variants], [exact_matching] diff --git a/formal_language b/formal_language @@ -14,6 +14,7 @@ A [set] of [words] over an [alphabet] - [slice]: [subset] of the [words] of a certain [length] - [density_function] - [language_unary] +- [formal_language_primality] - [computational_problems]: [formal_language_computational_problems] diff --git a/graph_basic_notions b/graph_basic_notions @@ -27,6 +27,7 @@ - [graph_representation] - [adjacency_matrix] - [adjacency_list] +- [line_graph] Up: [graph] diff --git a/graph_outerplanar b/graph_outerplanar @@ -0,0 +1,9 @@ +# Outerplanar graph + +https://en.wikipedia.org/wiki/Outerplanar_graph + +A [planar_graph] where all vertices are on the outer face of the drawing + +Up: [planar_graph] + +Aliases: outerplanar graph, outerplanar graphs diff --git a/graph_square b/graph_square @@ -4,6 +4,14 @@ Some are [Hamiltonian]: [graph_square_hamiltonian] +Three variants: +- connecting vertices with a distance *at most* two: this is the usual notion of graph square + - testing if an [undirected_graph] is a graph square in this sense is [NP_hard], cf [motwani1994computing] +- connecting vertices with a distance *exactly* two: studied in [bai2024characterizing] + - testing if an [undirected_graph] is a graph square in this sense is [PTIME] +- connecting vertices with a [walk] of length *exactly* two (but potentially also an edge): studied in [kutz2009digraph] + - testing if an [undirected_graph] is a graph square in this sense is [NP_hard] + Up: [graph_exponentiation] See also: [radoszewski2011hamiltonian], [graph_cube] diff --git a/graph_square_hamiltonian b/graph_square_hamiltonian @@ -2,6 +2,9 @@ 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 https://en.wikipedia.org/wiki/Graph_power#Computational_complexity Up: [graph_square] + +See also: [graph_square_hamiltonian_variants] diff --git a/greibachs_theorem b/greibachs_theorem @@ -0,0 +1,11 @@ +# Greibach's theorem + +https://en.wikipedia.org/wiki/Greibach%27s_theorem + +Can be used to show that deciding whether a [CFG] recognizes a [regular_language], or a [linear_CFL], is [undecidable] +- cf article [greibach1968note] +- cf https://cstheory.stackexchange.com/q/55586 + +Up: [context_free_grammar] + +See also: [Rice's_theorem], [bodirdski2024hereditary] diff --git a/join b/join @@ -5,5 +5,8 @@ - [join_path] - [self_join] - [optimal_joins] +- [inequality_join] Up: [databases] + +Aliases: joins diff --git a/line_graph b/line_graph @@ -0,0 +1,13 @@ +# Line graph + +https://en.wikipedia.org/wiki/Line_graph + +The *line graph* of an [undirected_graph] G = (V, E) is the [graph] G' where the [vertices] of G' are E and where there is an edge in G' connecting two edges of E if they share a vertex in G + +They can be recognized in [linear_time] + +They have a [Hamiltonian_cycle] if the original graph has a [Hamiltonian_cycle]: cf [balakrishnan2012textbook], Corollary 6.5.5 and [harary1965eulerian] + +Up: [graph_basic_notions] + +See also: [dual_hypergraph] diff --git a/matching b/matching @@ -3,7 +3,6 @@ Structure in [graph] et [graph_bipartite]: a subset of edges where no two edges share a vertex - [maximum_matching] -- [exact_matching] - [perfect_matching] Problems: @@ -15,8 +14,15 @@ Algorithms [graph_algorithm]: - [hungarian_algorithm] +Variants: + +- [matching_variants] +- [exact_matching] + Also the [linear_relaxation]: see [fractional_edge_packing] See also: [independent_set], [induced_matching], [graph_matching_covered], [deficiency] Up: [graph_substructure] + +Aliases: matchings diff --git a/nfa_equivalence b/nfa_equivalence @@ -0,0 +1,7 @@ +# NFA equivalence + +[PSPACE_complete] + +Up: [automaton_equivalence] on [NFAs] + +See also: [NFA_inclusion], [DFA_equivalence] diff --git a/nfa_inclusion b/nfa_inclusion @@ -0,0 +1,7 @@ +# NFA inclusion + +[PSPACE_complete] + +Up: [automaton_inclusion] for [NFAs] + +See also: [NFA_equivalence], [DFA_inclusion] diff --git a/open_world_query_answering b/open_world_query_answering @@ -1,7 +1,28 @@ # Open world query answering -Given a [database], [database_dependency] or [ontology], and [query], check if -it implied +This gets its name from the [open_world_semantics], which is that of databases +which may be missing some information. (Think of a [knowledge_base], like +[Wikidata]: you can hope that the facts of Wikidata are true, but there are +some true facts that are not in Wikidata.) You may have some integrity +constraints and reasoning rules (e.g., father(x,y) -> parent(x,y), or +locatedIn(x,y) locatedIn(y,z) -> locatedIn(x,z)) and the database doesn't +necessarily satisfy these constraints directly (e.g., some of the entailed +facts may not be materialized in the data) + +Formally, you have a [database] D, a set of database constraints Σ (e.g., +[database_dependencies], [integrity_constraints], an [ontology], etc.), and a +query Q. You want to consider all possible completions D' of D (i.e., D +subseteq D') subject to the constraints (i.e., D' \models Σ) and you want to +know whether all of these completions satisfy the query Q. (So that Q is not +necessarily true on D but is "entailed" in the sense that every completion of +D satisfying Σ must satisfy Q -- note that Q is typically monotone.) The +negation of the problem asks whether there is a counterexample model, i.e., a +completion D' of D that satisfies Σ but not Q (equivalently, that satisfies Σ +\land \neg Q). So this is the question of asking whether a superset of some +extensional data satisfies a logical formula (of a somewhat weird kind -- +typically Σ would consist of [tuple_generating_dependencies], +[existential_rules], or [description_logic] rules, whereas \neg Q would be the +negation of a [conjunctive_query] or [union_of_conjunctive_queries]). Also called "ontology-based data access", see also [ontology_mediated_query] @@ -12,9 +33,12 @@ Also called "ontology-based data access", see also [ontology_mediated_query] By [constraint_language]: - [open_world_query_answering_fds] - - [open_world_query_answering_rpqs] +Related to [query_containment] + +References: [imielinski1984incomplete], [arenas1999consistent], [cali2003decidability], [xiao2018ontology] + See also: [query_evaluation], [satisfiability], [open_world_semantics] Up: [database_theory] diff --git a/planar_graph b/planar_graph @@ -23,6 +23,10 @@ Specific algorithms: - [fkt_algorithm] +Special cases: + +- [graph_outerplanar] + Generalizations: - to [hypergraphs]: [planar_hypergraph] diff --git a/polytree b/polytree @@ -4,11 +4,11 @@ https://en.wikipedia.org/wiki/Polytree A polytree is a [directed_acyclic_graph] whose underlying [undirected_graph] is a [tree] -A polytree is always a [multitree] +A polytree is always a [multitree], but not vice-versa In a polytree, we can do [transitive_closure] in [output_linear] time, and do [enumeration] of reachable leaves with linear preprocessing and constant delay - this is like [boolean_matrix_multiplication] when there are no duplicate ways to obtain ones - - like [context_free_grammar_unambiguous] + - like [CFG_parsing] for [unambiguous_CFGs] - like [circuit] [deterministic] Up: [graph_family] diff --git a/primitive_word_language b/primitive_word_language @@ -10,6 +10,6 @@ Discussed in [lischke2011primitive] Up: [formal_language], [primitive_word] -See also: [square_language], [composite_word_language] +See also: [square_language], [composite_word_language], [formal_language_primality] Aliases: primitive words language diff --git a/regular_language b/regular_language @@ -34,6 +34,8 @@ - connection to [cycle_rank] of [automata] via [eggans_theorem] - [generalized_star_height] en ajoutant [complementation] - generalized star height of zero is [star_free_language] +- [state_complexity] +- [syntactic_complexity] ## Results diff --git a/rpq_simple_paths b/rpq_simple_paths @@ -8,6 +8,8 @@ For instance: - [simple_path_rpq_enumeration] - [rpq_counting_simple_paths] +It is tractable on [outerplanar_graphs] by [nedev2000polynomial] + Up: [rpq_semantics], [RPQ], [simple_paths] Aliases: RPQ simple path, simple path RPQ, simple path RPQs diff --git a/sharpp_hard b/sharpp_hard @@ -3,3 +3,5 @@ depends on the notion of [reduction]: [sharpP_Hard_reductions] Up: [hardness] for [sharpp] + +Aliases: sharpP_hardness diff --git a/shuffle b/shuffle @@ -8,3 +8,5 @@ A [word] w is a *shuffle* of two [words] u and v if we can interleave the charac - see [berstel2002shuffle] Up: [formal_language_operator] + +Aliases: interleaving diff --git a/simple_path_parity_problem b/simple_path_parity_problem @@ -0,0 +1,11 @@ +# Simple path parity problem + +[Computational_problem] of deciding if there is a [simple_path] in a [graph] from a vertex s to a vertex t that has even length (or odd length) + +This is [NP_complete] in general graphs by reduction from [two_disjoint_simple_path] + +But on [planar_graphs] it is in [PTIME] by [nedev1999finding] +- shown by reduction to [undirected_k_disjoint_path_problem] +- also and on [outerplanar_graphs] it is in [PTIME] even for [simple_path_RPQ] by [nedev2000polynomial] + +Up: [simple_path_problem] diff --git a/simple_path_problem b/simple_path_problem @@ -5,5 +5,6 @@ Obviously [PTIME] by computing a [shortest_path] - [simple_path_rpq_problem] +- [simple_path_parity_problem] Up: [computational_problem], [simple_path] diff --git a/syntactic_complexity b/syntactic_complexity @@ -0,0 +1,9 @@ +# Syntactic complexity + +The cardinality of the [syntactic_semigroup] of a [regular_language] + +Studied for instance in [brzozowski2012syntactic] + +Up: [regular_language] + +See also: [state_complexity] diff --git a/tuple_generating_dependency b/tuple_generating_dependency @@ -36,4 +36,4 @@ Up: [database_dependency] See also: [datalogpm], [denial_constraint] -Aliases: TGD, TGDs +Aliases: TGD, TGDs, tuple generating dependencies diff --git a/underlying_undirected_graph b/underlying_undirected_graph @@ -1,8 +1,11 @@ # Underlying undirected graph -Given a [directed_graph] G = (V, E), construct an [undirected_graph] G' = (V, E') by taking E' = {{u, v} \mid (u,v) \in E}. +Given a [directed_graph] G = (V, E), its *underlying undirected graph* is the +[undirected_graph] G' = (V, E') obtained by taking E' = {{u, v} \mid (u,v) \in +E}. - May contain [multiedges] if some vertices are connected by an edge in both directions - May contain [self_loops] if G did +- We may alternatively define G' as an [undirected_graph] without [multiedges] or [self_loops] by discarding [self_loops] and multiple edge occurrences Up: [graph_operations] diff --git a/vector_addition_system b/vector_addition_system @@ -11,6 +11,7 @@ Also called "vector addition system with states" (VASS) Generalizations: - [vector_addition_tree_automata] - [vector_addition_system_pushdown] +- [vector_addition_system_nested] Complexity of the [reachability] problem: [ackermann_function] - https://www.quantamagazine.org/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204/ diff --git a/vector_addition_system_nested b/vector_addition_system_nested @@ -0,0 +1,7 @@ +# VASS with nested zero tests + +studied in [guttenberg2025reachability] + +Up: [vector_addition_system] + +Aliases: VASS with nested zero tests diff --git a/xsat b/xsat @@ -4,6 +4,8 @@ A [Boolean_satisfiability_problem] formed as a [conjunction] of [clauses], in ea Also called "1-in-3-SAT" in the case of [3SAT] +Relevant: https://cstheory.stackexchange.com/q/32208 + Up: [sat_variants] See also: [exact_cover], [hitting_set]