commit 6aa32b524ee93a7ff16d144bd64a4d637bb3f311
parent bb4c47dac2cbc9dc606e4f81df2ee4b73b61e50c
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sun, 9 Mar 2025 20:38:43 +0100
commit with codex
Diffstat:
2 files changed, 18 insertions(+), 2 deletions(-)
diff --git a/approximation_class b/approximation_class
@@ -1,9 +1,9 @@
# Approximation classes
- [FPRAS]: for all epsilon you have an [algorithm_randomized] running in polynomial time in 1/e and in the input, with a probability delta of failure
- - variant QPRAS [qpras] with "quasi-polynomial time" [quasipolynomial]
+ - variant [QPRAS] with [quasi-polynomial] time
- [PRAS]: same but not polynomial in 1/e
-- without R, a deterministic algorithm (PRAS vs [PTAS], FPRAS vs [FPTAS])
+- without R, a deterministic algorithm ([PRAS] vs [PTAS], [FPRAS] vs [FPTAS])
- [APX]: there is an [approximation_algorithm] for a certain fixed epsilon
Up: [complexity_class] of [approximation]
diff --git a/locally_threshold_testable_language b/locally_threshold_testable_language
@@ -0,0 +1,16 @@
+# Locally_threshold_testable_language
+
+Discussed in [bojanczyk2007new]
+
+A [formal_language] is *locally threshold testable* if it is a [Boolean_combination] of [formal_languages] of the form:
+- words having a given [word] w as a [prefix]
+- words having a given [word] w as a [suffix]
+- words having a given [word] w as a [factor] at least n times
+
+Generalizes [locally_testable_languages]
+
+Up: [locally_testable_language]
+
+See also: [local_language]
+
+Aliases: LTT language, LTT
