commit 00c1b56dccfd065ebf6f92e8d28f8c72eb5f3a50
parent 19e1dc5c3e83c41fb9c31da689d8e768a5e6dd05
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 9 Oct 2026 00:19:19 +0200
commit with codex
Diffstat:
16 files changed, 45 insertions(+), 11 deletions(-)
diff --git a/automaton_intersection b/automaton_intersection
@@ -7,4 +7,4 @@ can be done with [product_construction]
Up: [automaton_constructions], [language_intersection]
-See also: [regular_expression_conjunction], [CFG_intersection]
+See also: [regular_expression_conjunction], [CFG_intersection], [intersection_nonemptiness]
diff --git a/chase_termination b/chase_termination
@@ -4,7 +4,7 @@ depends on the kind of [chase]:
- [chase_oblivious]: [oblivious_chase_termination]
- [chase_restricted]: [restricted_chase_termination]
-depends on whether you want all instances or an input instance
+depends on whether you want [all_instance_termination] or [data_dependent_chase_termination]
[academic_papers]:
- [gogacz2014all]
diff --git a/chromatic_number b/chromatic_number
@@ -0,0 +1,7 @@
+# Chromatic number
+
+The least number of colors for [graph_coloring] of a graph
+
+[chromatic_number_computation]
+
+Up: [graph_coloring], [graph_parameter]
diff --git a/chromatic_number_computation b/chromatic_number_computation
@@ -0,0 +1,5 @@
+# Chromatic number computation
+
+The [computation_problem], given an [undirected_graph], of computing its [chromatic_number]
+
+Up: [computation_problem], [chromatic_number]
diff --git a/circuit_parameter b/circuit_parameter
@@ -6,3 +6,5 @@
- [circuit_size]
Up: [parameter] of [circuit]
+
+See also: [graph_parameter]
diff --git a/complexity_class b/complexity_class
@@ -25,6 +25,7 @@
- [l_poly] L/poly
- [optimization_problem]
- [NPO]
+- [incremental_complexity]
## Results
diff --git a/graph_coloring b/graph_coloring
@@ -26,12 +26,7 @@
## Complexity
-- [np_complete], already for [graph_planar] and [4_regular] graphs
- - [np_complete] to find if it is 3 or 4
- - 4 colors on [planar_graph] is always feasible by the [four_color_theorem]
-- [3_coloring] is in [linear_time] by [Brook's_theorem] on [graphs] of maximal [degree] 3
- - see https://cstheory.stackexchange.com/questions/51368/which-hypergraphs-can-be-simplified-by-alternatively-removing-a-hyperedge-and-an
-- [bipartiteness_testing] (k=2)
+[graph_coloring_computation]
## Constructions
diff --git a/grid_minor b/grid_minor
@@ -12,6 +12,6 @@ used for [hardness] results, e.g., [grohe2007complexity]
Up: [theorem] about [grid_graph]
-See also: [grid_minor_directed], [treewidth]
+See also: [grid_minor_directed], [treewidth], [polynomial_grid_minor_theorem]
Aliases: grid minor extraction, grid extraction
diff --git a/hypertree_width_computation b/hypertree_width_computation
@@ -0,0 +1,9 @@
+# Hypertree width computation
+
+for any k, we can determine in [PTIME] whether an input [hypergraph] has [hypertreewidth] <= k, and if so compute a [hypertree_decomposition]: [gottlob2002hypertree]
+
+[parameterized_complexity]: [gottlob2005hypertree]
+
+Up: [hypertree_width], [computation_problem]
+
+See also: [treewidth_computation]
diff --git a/hypertree_width_variants b/hypertree_width_variants
@@ -2,7 +2,7 @@
- [generalized_hypertree_width], with [edge_cover]
- [hypertree_width] (and [hypertree_decomposition]) with [special_condition] on the projected variables
- - makes [tree_decomposition_computation] easier
+ - makes [hypertree_width_computation] and [tree_decomposition_computation] easier
- [query_decomposition]
all are within a factor 3 of each other, cf [adler2007hypertree] and [gottlob2007generalized]
diff --git a/linear_extension b/linear_extension
@@ -7,3 +7,5 @@ Asymptotics of the number of elements required to achieve a specific number of l
Up: [partial_order]
Aliases: linear extensions
+
+See also: [order_polynomial]
diff --git a/linear_extension_counting b/linear_extension_counting
@@ -3,4 +3,6 @@
[brightwell1991counting]: it's [SharpP_complete]
- also for [height_2_posets], cf [dittmer2018counting]
+It is [W1_hard] when parameterized by the [treewidth] of the [cover_graph], cf [eiben2019counting]
+
Up: [counting_problem], [linear_extension]
diff --git a/property_testing_formal_language b/property_testing_formal_language
@@ -15,6 +15,7 @@
- [francois2015streaming] on [visibly_pushdown_languages]
- [fischer2010approximate] for [edit_distance_with_moves]
- called "approximate satisfiability"
+- [jackman2026query] for [dyck_languages] and generalizations
Up: [property_testing], [formal_language]
diff --git a/pspace_complete b/pspace_complete
@@ -2,4 +2,7 @@
The class of [computational_problems] that are in [PSPACE] and [PSPACE_hard]
+- [QBF_SAT]
+- [NFA_universality]
+
Up: [pspace]
diff --git a/qbf_sat b/qbf_sat
@@ -0,0 +1,7 @@
+# QBF SAT
+
+[SAT] on [QBF]
+
+It is [PSPACE_complete]
+
+Up: [QBF], [SAT]
diff --git a/treelike_data b/treelike_data
@@ -6,4 +6,4 @@ On such data we can do [pqe_mso]
Up: [data] of bounded [treewidth], [types_of_data]
-See also: [bounded_treewidth_graph], [pathlike_data]
+See also: [bounded_treewidth_graph], [pathlike_data], [bounded_treewidth_sets]
