commit e382e8dbb1b60350acce119915c6045b6dbda291
parent 6a3902c06284558791308770071f922c40a3546f
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sun, 30 Mar 2025 10:44:55 +0200
commit with codex
Diffstat:
18 files changed, 111 insertions(+), 21 deletions(-)
diff --git a/bpp b/bpp
@@ -2,6 +2,8 @@
Class BPP: [algorithm_randomized] for [decision_problem] with [two_sided_error] can err in both directions with proba 1/4. The error probability can be made exponentially small by retrying
+It is known that [PTIME] is included in BPP; the converse implication is not known
+
it is not known if BPP is contained in [nptime]
It is known that if [nptime] subseteq BPP then in fact [nptime] = [rp] : if you have an
@@ -11,7 +13,7 @@ you can remove errors on one side (uses [self_reducibility])
[sipser_lautemann_theorem]: It is known that BPP is in [sigma2_cap_pi2]: https://en.wikipedia.org/wiki/Sipser%E2%80%93Lautemann_theorem
- as BPP is closed under [complementation] it suffices to show that it is in [sigma2]
-Analogue [bpl] BPL with logarithmic space condition
+Analogue [BPL] with logarithmic space condition
Corresponding notion of [algorithm] running in [ptime]: "[monte_carlo_algorithm] with bounded probability of two-sided error"
diff --git a/circuit b/circuit
@@ -14,6 +14,8 @@
- [probabilistic_circuit]
- [Semiring_circuit]
- [formula]
+- [circuit_monotone]
+- [circuit_positive]
## Problems
@@ -51,6 +53,6 @@
Up: [theoretical_computer_science]
-See also: [sum_product_network]
+See also: [sum_product_network], [formula]
Aliases: circuits
diff --git a/complexity_time_classes b/complexity_time_classes
@@ -0,0 +1,21 @@
+# Complexity time classes
+
+- [ptime] / [p_complete]
+ - [linear_time], [linear_time_nearly], [linear_time_almost]
+- [np_intermediate], cf [ladners_theorem]
+- [nptime]
+ - [conptime]
+ - [np_cap_conp]
+- [exptime]
+ - [nexptime]
+ - [2exptime]
+ - [TOWER]
+- [PP]
+- [PSPACE]
+ - [pspace_complete]
+- [oplusP]
+- [US]
+
+Up: [complexity_class], [complexity_time]
+
+Aliases: time complexity class, time complexity classes
diff --git a/connectivity b/connectivity
@@ -11,6 +11,7 @@ Problem of knowing how many edges/vertices you must remove from a [graph] in ord
- [strongly_connected_graph]
- [weakly_connected_graph]
+- [connectivity_circuit]
See also: [mengers_theorem], [minimum_cut], [connected_graph]
diff --git a/cut b/cut
@@ -0,0 +1,13 @@
+# Cut
+
+In a [graph], a *cut* is a [partition] of the [vertices] in two sets
+- There may be a source s and a sink t, and then an *st-cut* is one where the source is on one side and the sink is on the other side
+- The graph may be [graph_directed] or [graph_undirected]
+ - The correspondance to [network_flow] is in the case of [graph_directed]
+- An [ideal_cut] is one where there is no [edge] at all going from the right side to the left side
+
+- [cut_ranked_enumeration]
+
+Up: [network_flow]
+
+Aliases: cuts, network cut, network cuts
diff --git a/cut_ranked_enumeration b/cut_ranked_enumeration
@@ -0,0 +1,10 @@
+# Cut ranked enumeration
+
+[Enumeration] of [cuts] with [polynomial_delay]
+
+- [picard1979structure]
+- [vazirani1992suboptimal]
+
+Up: [ranked_enumeration] of [cut]
+
+See also: [beideman2022deterministic]
diff --git a/cutwidth_directed b/cutwidth_directed
@@ -0,0 +1,5 @@
+# Cutwidth directed
+
+introduced in [chudnowski2012tournament]
+
+Up: [cutwidth] on [directed_graphs]
diff --git a/graph_directed b/graph_directed
@@ -1,6 +1,6 @@
# Graph directed
-A [graph] where [edges] are [directed_edges] [ordered_pairs]
+A [graph] where [edges] are [directed_edges]
- [directed_acyclic_graph]
- [graph_period]
@@ -8,6 +8,6 @@ A [graph] where [edges] are [directed_edges] [ordered_pairs]
Up: [graph]
-See also: [graph_undirected], [directed_edge]
+See also: [graph_undirected], [directed_edge], [graph_oriented]
Aliases: directed graph, directed graphs
diff --git a/graph_minor b/graph_minor
@@ -4,6 +4,8 @@
[graph_minor_testing]
+- [graph_immersion]
+
Up: [graph]
See also: [robertson_seymour], [topological_minor], [excluded_minor], [forbidden_minor], [induced_minor]
diff --git a/pathwidth_computation b/pathwidth_computation
@@ -6,6 +6,7 @@ https://en.wikipedia.org/wiki/Pathwidth#Special_classes_of_graphs
- Is [NP_complete] even on [bounded_degree] [planar_graphs]
- Can be computed in [linear_time] for [trees] and [forests]
- Can be computed in [polynomial_time] for [treelike] [graphs]
+- Is [NP_complete] on [weighted_trees], cf [mihai2009pathwidth]
- [pathwidth_approximation]
diff --git a/ptime b/ptime
@@ -1,16 +0,0 @@
-# PTIME
-
-[ptime_complete]
-
-When the input consists of integers, we distinguish: https://en.wikipedia.org/wiki/Time_complexity#Strongly_and_weakly_polynomial_time
-- "strongly polynomial" which means
- - polynomial in the number of inputs
- - the memory used in polynomial in the size of the input
-- "weakly polynomial" meaning polynomial in the number of integers and in the log of integers, e.g., [euclidean_algorithm], not just polynomial in the number of integers
-- not to be confused with [pseudo_polynomial_time]!!
-
-Up: [complexity_class]
-
-See also: [pseudo_polynomial_time], [quasipolynomial], [oplusp], [ptime_reduction]
-
-Aliases: P, polynomial time
diff --git a/self_reducibility b/self_reducibility
@@ -0,0 +1,8 @@
+# Self-reducibility
+
+https://en.wikipedia.org/wiki/Function_problem#Self-reducibility
+
+The paper [jerrum1986random] that defines it shows equivalence of [counting_approximate] and [sampling_approximate]
+- it also shows that [counting_approximate] to within a constant factor allows you, for self-reducible problems, to do [counting_approximate] with a [fpras], by going via [sampling_approximate]
+
+Up: [theoretical_computer_science]
diff --git a/tree b/tree
@@ -69,6 +69,7 @@
- [polytree]
- [multitree]
- [out_tree] as a [directed_graph]
+- [tree_weighted]
Up: [data_structure]
diff --git a/tree_cut_width b/tree_cut_width
@@ -0,0 +1,5 @@
+# Tree cut width
+
+discussed in [ganian2022algorithmic]
+
+Up: [width_measure]
diff --git a/tree_weighted b/tree_weighted
@@ -0,0 +1,7 @@
+# Tree weighted
+
+A [tree] featuring [weights]
+
+Up: [tree]
+
+Aliases: weighted tree, weighted trees
diff --git a/up b/up
@@ -7,6 +7,8 @@ https://complexityzoo.net/Complexity_Zoo:U#up
- on negative instances, all [runs] are rejecting
- on positive instances, exactly one [run] accepts
-Generalization: [FewP]
+Generalizations:
+- [FewP]
+- [US]
Up: [nptime], [unambiguity], [complexity_class]
diff --git a/us b/us
@@ -0,0 +1,11 @@
+# US
+
+https://complexityzoo.net/Complexity_Zoo:U#us
+
+The [complexity_time_class] of [decision_problems] definable with a [nondeterministic_PTIME_Turing_machine] that accepts when there is precisely one [accepting_run]
+
+It is a superset of [UP]
+
+Up: [complexity_time_classes]
+
+See also: [XNFA]
diff --git a/word_automaton_exclusive b/word_automaton_exclusive
@@ -0,0 +1,15 @@
+# Word automaton exclusive (XNFA)
+
+Like an [NFA] but accept the words for which there is precisely one [accepting_run]
+
+Every [UFA] is an XNFA
+
+[Academic_papers]:
+- [kutrib2024complexity], which is about [word_automaton_exclusive_unary]
+- [kutrib2023complexity]
+
+Related to the [time_complexity_class] [US]
+
+Up: [word_automaton_unambiguous]
+
+Aliases: XNFA
