正则闭集：描述与计算的关系

65《理论计算机科学电子札记》66卷第1期（2002年）网址：http://www.elsevier.nl/locate/entcs/volume66.html14页正则闭集彼得·赫特林1Theoretische InformatikIFernuniversitaüt Hagen58084 Hagen德国摘要Ziegler [8]收集并系统地比较了描述欧氏空间的正则闭子集的许多不同方法。我们更详细地分析了Ziegler提出的正则闭集的一种特别弱的表示与其他表示之间的关系。这种弱表示允许在描述中产生一定量的错误1介绍如果希望通过计算机对给定类之外的对象执行计算，则必须选择一种通过位串来表示这些对象的方式这意味着人们必须清楚地知道关于对象的哪种信息是可用的或期望给定可数类之外的对象通常可以用有限字符这是不可能的，如果一个考虑对象的不可数类，例如，真实的数字。但是如果类的基数不大于实数集的基数，那么我们可以使用有限位序列或自然数序列这是“E-2型理论”的基本思想之一;见Weihrauch [5，6]。很明显，表示的选择极大地影响了对象的可计算性。在本文中，我们感兴趣的是正则闭集。这样的集合，特别是凸定期封闭集，出现在许多计算问题的几何和优化;见例如。Gro？tschel，Lov'asz，anddSchrijver[3]orZiegler and Brattka [9].由于在不同的问题中，关于集合的不同种类的信息要么是可用的，要么是要计算的，因此需要对这些集合的各种表示进行Ziegler [8]收集1电子邮件：peter. fernuni-hagen.de2002年由ElsevierScienceB出版。 诉 操作访问根据C CB Y-NC-N D许可证进行。赫特林66⊆→≥⊆并比较了欧氏空间的正则闭子集和正则闭凸集的一些表示他表明，他们中的许多人然后，他把这些他指出，正表征的类别形成了一个层次，在这个意义上，“较强”的表征可以被还原为“较弱”的从相对于某个“较强”表示的名称中包含的信息对于负表示类也是如此此外，这些类别大多是相互独立的：人们不能将消极的表征还原为积极的表征，反之亦然，只有一个令人惊讶的齐格勒表明，人们可以把一个相当强的负表示还原为最弱的正表示，并且通过对偶，把一个相应的相当强的正表示还原为最弱的负表示。在本文中，我们调查是否也较弱的负信息是足够的，以获得最弱的正信息。首先，我们证明了一个猜想齐格勒，这是不可能的，即使一个限制自己的名称定期关闭，紧凑，凸集或名称的nonempty，定期关闭集。然后，我们表明，相反的是真的，如果考虑定期关闭，凸集没有空集：然后可以减少甚至第二个最弱的负表示最弱的正表示。最后，我们表明，即使一个限制自己的定期关闭，紧凑，凸集没有空集不能减少最弱的负表示最弱的正表示。我们还解释了哪些积极的表示可以减少到消极的表示。第2节包含必要的定义。第三节给出了Ziegler [8]引入的正则闭集表示与本文结果第四节是本文结果的证明最后，第5节给出了一些动机，为什么这里考虑的表示可能是有趣的。2定义首先是一些符号。我们用N表示自然数的集合，即，非负整数，由Q的有理数的集合，和由R的实数的集合。对于两个集合X和Y，我们用f：XY表示一个（可能是部分的）函数，其定义域dom（f）是X的子集，其值域是Y的子集。如果f的定义域等于X，即，如果f是全的，我们可以写f：X→Y来表示。让我们固定一个整数d1。一个子集RRd称为正则闭的，如果它等于它内部的闭包以下是两个基本的观察者--赫特林67⊆⊆→⊆→∈ ∈−| |{ |→ }⊆→||−∈{∈|∃||}vations将用于以后的建设表示的定期关闭集。引理2.1对于子集RRd，以下三个条件是等价的：(i) R等于其内部的闭包。(ii) 存在一个开集U，其中R =闭包（U）。(iii) 存在一个闭集A，R =闭包（内部（A））。引理2.2闭集的补集的闭包是正则闭的。正则闭集R的补集的闭包的补集的闭包等于R。我们将特别感兴趣的是凸正则闭集。 记住，一个子集的Rd被称为凸的，如果与任何两个点，它也包含所有点的直线段之间的两点。如果一个人希望执行计算涉及定期关闭集，一个人必须有一个清晰的想法，什么样的信息集是可用的，什么样的信息，一个人希望计算，以及如何在计算机中表示这些信息。通常，为了唯一地表示一个正则闭集，需要无限数量的信息。涉及无限信息量的计算是E-2型理论的主题;参见Weihrauch[5，6]。在[6]中，像R的闭子集这样的对象通常由无限二进制序列表示。但是，如[5]所示，同样可以使用自然数的有限序列。为了便于记法，我们将使用基于自然数无穷序列的表示法集合X的表示是满射函数ρ：BX，其中B：=p p：N N是所有自然数无穷序列的空间，赋予N上离散拓扑的乘积拓扑。例2.3例如，N的幂集2 N的全表示En：B → 2 N定义为En（p）：={n∈N|（<$i∈N）p（i）= n +1}对所有p∈ B.类似地，我们定义En（w）：= nN（i w）w（i）=n+ 1 对于任何w= w（0）. w（w第一章其中，N表示所有有限字符串的集合自然数和w是有限字符串的长度w。另一个符号：对于pB和n我们用pTn表示p（0）的前缀. p（n1）的长度n的p。我们想比较一下表象。因此，我们在B上使用可计算或连续函数。函数F：B B是可计算的，如果存在可计算单调函数f：N<$N<$（单调性意味着f（v）是f（w）的前缀，如果v是w的前缀，并且f（v）和f（w）都被定义），dom（F）={p ∈ B|（<$n ∈ N）（<$m ∈ N）|f（p T m）|≥ n}，f（p T m）是F（p）的一个前缀，只要p∈ dom（F）且p T m∈ dom（f）.赫特林68⊆→Q⊆→≡⊆→≡⊆ →∈⟨ ⟩·QQ⟨⟩DQQ<<<0}的所有位置有理数由yv+（i，k）：=（i+1）/（k+1）定义。一个标准数为νd：N→Qd其中R d中的有理点的个数定义为νd（i1，...，id）：=（vQ（i1），.，νQ（id））。Rd中所有有理立方体的标准编号Cd定义为：Cd（n =1，.， id，j1，.，（ jd）：={x=（x1. ，xd）∈Rd||νQ（ik）−xk|对于<所有k∈{1， . ，d}}。如果维度d在上下文中很清楚，我们通常将其写成C而不是D。Cd.我们把Cd（n）写成Cd（n）的闭包。此外，我们经常编写Cn对于C（n）和Cn对于C（n）。在这些准备之后，我们可以引入正则闭集的各种表示。首先，我们介绍闭集或开集的两个基本表示;见[7，2，4，6]。设d≥1是固定的。(i) Rd的所有闭子集的表示ρ闭定义为：ρclosed（p）= A En（p）={i ∈ N |Cd（i）{A/= A}。(ii) Rd的所有开子集的表示ρopen定义为：ρopen（p）= U En（p）={i ∈ N |C（i）U}。Ziegler [8]利用引理2.1，在这些（确切地说是等价的）表示的基础上，给出了Rd的所有正则闭子集的集合的几个在下文中，我们用Rd表示Rd的所有正则闭子集的集合。在以下定义中R的四个表示θd，θd，θd，θd，我们遵循Ziegler请注意，第一个定义的意思是没有别的，只是关闭：= ρ|Rd，即，布吕德通过将ρ闭限制为Rd的正则闭子集的名称来定义。为p∈B和R∈ Rd，我们定义：赫特林69<<<<}Q{∈||∈}→{∈<ν<>><<<><−B−><<>>><>下图。这里，对于图中的任何表示γ和δ✟✟✟✯布吕德❍❍❍❥D❍❍❍❥✟✟✟✯ν<ν✲<✟✟✟✯D❍❍❍❥埃克塞特✻❄ϑ◦νFig. 1. 正表示Ziegler [8]已经证明，如果有从γ指向δ的箭头，则γ如果没有从γ指向δ的箭头，则γ/”t δ。请注意，这两个代表-sentations_。 通过对偶性，人们可以得到一个类似的消极表达的层次结构。θdψ>✟✟✟✯D❍❍❍❥ν>❍❍❍❥✟✟✟✯ν✲>✟✟✟✯布吕德❍❍❍❥>✻❄ϑ◦ν图二. 否定表示人们现在可能会认为，积极和消极的表示是不可比的，即，否定的表示不能还原为肯定的表示，肯定的表示不能还原为否定的表示。令人惊讶的是，这几乎是但不完全正确的。首先，我们将考虑从否定表示到肯定表示的可归约性。一方面，[8，定理4.12b]的证明表明，布吕德|Bd\{n}/”t d|Bd，（1）其中d表示[1，1]d的所有正则闭凸子集的集合。这意味着，最强的负表示d不能连续地约化为第二弱的正表示d，即使限制为[1，1]d的非空凸正则闭子集的名称。另一方面，齐格勒还表明：埃克塞特 “你好。（二）这意味着，“正”的双原子名是如此的弱，以至于它们可以从“负”的双原子名推导出来。但Ziegler [8]指出，弱于非负更确切地说，他强调，以下第定理成立。定理3.1（i）|Bd/“ |Bd.(ii) ϑν|Rd\{n}/”>不 <埃克塞特|Rd\{n}。θθψψϑϑθ不 <<<<>>赫特林71><>R联系我们><<联系我们><<><><在这个定理的第一部分，我们假设空集也是正则闭的和凸的。如果一个人不希望假设这一点，然后基本陈述的定理表示的第二部分theo-雷姆。注意，图1和图2、陈述（1）和（2）以及定理3.1完整地描述了从负表示到正表示RD。他们还表明，如果限制这些，情况也是一样的。表示的集合的名称在Bd。但是，空集在定理3.1的第一个陈述的证明中起着重要的作用如果我们排除空集，只考虑非空的正则集，闭凸集是表示ν限制到这样的集合可约去查伯德？确实是我们证明，对于这样的集合，即使是一个较弱的负表示，即第二弱的负表示θ∈d，可约化为最弱正表示θ∈v。我们用C表示>不 <θd |Bd。这些结果完整地描述了Cd和Bd从负表示到正表示的约化.哪些正表示可还原为负表示？如果考虑任意规则闭集的表示，即，d，则通过图1和图2的对偶性，从（1），从（2），从（3），从（4），从（5），从（6），从（7），从（8），从（9），(2)定理3.1现在，让我们将表示限制为凸集的名称。我们注意到，与（1）类似，可以很容易地证明角θd|Bd\{t}/”t θ d|Bd。（三）因此，没有一个正表示可以被简化为第二弱的负表示，即使是在仅限于d中集合的名称时。此外，通过对偶性，从（2）d“。（四）Ziegler [8]还证明了，仅限于凸正则闭的名称Rd的子集，可约化为Rd的五个正表示（请参阅图1）都是等价的，其中θd。图中的最后一部分由定理3.3提供（二）.因此，当仅限于Cd或d中的集合名称时，除了最弱的一个外，所有的正表示都可以归约为最弱的负表示。θ不赫特林72>⊆→><ν><2LN2LNnn4样张本节包含定理3.1、定理3.2和定理3.3的证明。定理3.1证明的思想类似于[1，定理22]中单向(i) 为了简单起见，我们只证明了d= 1的情况。显然，对于任意的d，我们可以用同样的方法证明这个命题。为了避免矛盾，我们假设存在一个连续函数F：B B，它映射的是R到一个记住一个名字<>是所有i的列表，其中ν（i）/∈R。对于定义埃克塞特 参见第2节。我们将构造空集的一个空F（r）是包含整个单位区间[0，1]的闭集的一个集合这是一个矛盾，因为闭集的内部包含开单位区间，而闭集的内部应该是空的。下面我们归纳地定义了三个自然数序列（ln）n、（kn）n和（jn）n，两个字符串序列（un）n和（vn）n，以及序列pn∈B的序列（pn）n，具有以下性质：• 闭区间序列Cjn在[0， 1]中是稠密的，即，[0，1]的任何开子集包含一些Cjn，•你... un−1pn是C j n的一个n>-名，对所有n，• un是pn的前缀，对于所有n，• En（u0. un）包含所有j≤n，其中ν（j）∈R\Cjn，对所有n，• F（u0. unB）brief0. vnB，对于所有n，• v0... vn包含jn，对于所有n。所有这些序列将被归纳地定义为阶段n = 0，1，2，..。. .雄鹿;雄鹿 Setln：=[log2（n+1）and dkn：=n+1−2ln.Choosea数jn使得Cj≠kn，kn+1cj不包含任何v（i），i∈ En（u0. un−1）。然后字符串u0ν... un−1可以扩展为一个名ν的区间Cjn，即， 存在某个pn∈ B使得<$0>（u0. un−1pn）=Cjn.通过归纳假设，我们知道F（u0. un−1pn）∈v0. vn−1B.设vn是N中最短的字符串，使得F（u0. un−1pn）∈v0. vnB，使得jn∈E n（v0. vn）。 这样的vn必须存在，因为F（u0. n-1pn）是一个C j的一个名字，因此，一个闭集的一个与Cjn 的非空交集。此外，设un是p n的最短前缀，使得En（u0. un）包含所有j≤n，其中ν（j）∈R\Cjn，且使得F（u0. unB）brief0. vnB. 这样的一个前缀存在，因为u0... un−1pn是一个名为C.这就结束了对阶段n的描述。很明显，以这种方式定义的序列具有上述性质。现在我们定义r：=u0u1u2.. . .则En（r）= dom（v），即r∈>>∈|>∈列出了所有数ν（j），其中j为m（ν）。 因此，r是空的一个空集通过假设，F（r）是空集的空名，因此，<<一个封闭的集合A，它的内部是空的。 另一方面，通过F的连续性，我们有F（r）= v0v1v2。. . 让我们固定一个任意点y∈[0，1]。 序列v0v1v2... 列出半径任意小的有理立方体，任意接近y。因此A必须包含任意接近y的点。因为A是封闭的，所以它也必须包含y。因为这对任意y∈[0， 1]都是真的，所以我们证明了[0， 1]<$A。正如上面所解释的，这是一个矛盾。(ii) 在定理第一部分的证明中，我们在d= 1的情况下使用了这样的假设，即所考虑的表示被定义在包含在区间[0，1]中的非空紧区间和空集上。对于更大的d，我们可以很容易地用紧立方体和空集给出本质上相同的证明虽然很明显，紧致立方体是规则闭的和凸的，但人们可能不太高兴空集在这里起我们留给读者去检查，如果用集合[2，3]代替空集，那么在d= 1的情况下，证明也是有效的。区间序列Cjn由集合序列Cjn<$[2， 3]构成，其中序列（jn）n和其他序列的定义与前面类似。 同样一个可以进行更大的d。这给出了定理的第二个断言的证明。✷定理3.2的证明记住，一个正则闭集R的θ-d我们描述了一个算法，显示减少。我们只描述它对于输入pdom（θd Cd\{n}）。我们可以假设R：非空，正则闭，凸集。角θd|Cd\{p}是a首先，我们定义N的有限子集的序列（Sn）n。固定某个n∈N。我们称一个子集B为好的，如果它不包含任何迄今为止由p枚举的开有理立方体，即，如果不存在j∈En（pTn）且B<$Cj.设Sn是字典式定义的y∈f{0， . ，n}，因此，- 让我们称之为H（Sn）-的集合i∈SnCi是好的。 在这里，第一“具有以下含义：w e ide n tif y ea c h subse t S of { 0，. ，n}，其中n + 1位字符串r S（0）... rS（n）定义为如果是S，rS（i）：=01否则。并对所有n+1位串应用通常的字典排序显然，给定p，可以在n中均匀地计算集合Sn。因此，给定p，通过..Σ.En（r）=j∈dom（ν. n≥j）ν（j）∈Ci.）的。（一）.i∈Sn赫特林74<<∈{−}{}{|∈}我们称这样一个序列r是一个|Cd\{n}-集合R的名称。我们从一个技术要求开始证明算法的正确性：集合序列（Sn）n逐点收敛到集合T：={i ∈ N |Ci R}。这意味着，对于每个m∈N，存在一些Nm∈N，使得Sn{0， .， m−1}=T{0， .. . ， m−1}，其中n≥Nm。我们用m上的归纳法证明了这一点。请注意，对于m=0，这显然是正确的：设置N0：= 0。我们假设它对m成立，并证明它对m+1也成立。第一种情况：m∈T。设Nm+1：= max {Nm，m}，并考虑任意n≥Nm+1。通过归纳推理，Sn={0， . ， m−1}=T{0， .. . ， m−1}。因为MT，由于R是凸的，H（Sn0，.，M1米）的R. 由于R不包含任何由p枚举的开有理立方体，我们得出结论Sn已经包含m。第二种情况：m/∈T。然后是Cm/ΔR。由于R是闭的，这意味着Cm/<$R，因此Cm与R的补有非空交，特别是Cm与R的内部的补有非空交。因此，立方体Cm必须由p枚举，即，一定有某个l满足m+1 =p（l）。断言遵循Nm+1：=max{Nm，l}。我们证明了集合Sn的收敛性.我们来到正确性证明的主要部分我们必须证明r是R的一个v设D：=ν（j）jEn（r）。 我们将展示以下两个声明：(i) 集合D包含R内部的所有点ν（j）。(ii) 集合D在R之外没有任何聚点。对于第一个要求，固定一个数j，使得ν（j）位于R的内部。则存在某个i使得ν（j）∈Ci且Ci包含在R中.由于关于集合Sn的收敛性的主张，对于所有极大的n，n个集合将在Sn中收敛。Sincev（j）∈Ci，对于所有的子集，我们将有ν（j）∈i∈SnCi。 因此，ν（j）∈D。对于第二个要求，假设D有一些聚集点z在钢筋混凝则存在En（r）中的严格递增数列（jk）k，使得点ν（jk）收敛于z，并且存在序列（nk）k，nk≥jk，且对所有k，ν（jk）∈i∈SnkCi.设l是一个任意数，R包含立方体Cl。由于关于集合Sn的收敛性的主张，对于所有极大的k，集合Snk包含l，因此，H（Snk）包含Cl。设HJ是Cl和z的凸包.因为我们假设z在在闭集R中，存在包含在HJ∈（Rd\R）中的某个有理立方体让Cm是具有相同中点但只有一半边长的有理立方体则Cm包含在Hj（Rd\R）的内部.赫特林75<><>>2N>2N2N2N<<<<集合An，其中n∈N：An：=（−∞，−1].Σ（0，1）n{v（i）|i∈{0， . ， n−1} 随机数（ν）}[1，∞）。注意，所有这些集合都满足闭包（interior（An））=（−∞，−1]<$[1，∞）=闭包（R\[−1，1]）。设f个序列pn∈B，其中En（pn）={j∈ dom（ν）|v（j）∈An}.下面我们归纳地定义了两个字符串序列（un）n和（vn）n，它们对所有n都具有以下性质。• un是pn的前缀。• En（u0. un）包含所有j< n，其中ν（j）∈An.• F（u0. unB）brief0. vnB.• 对于{0， . ，2n-1}，其中至少有一个j∈En（v0.. . vn）withCji，i+1。这两个序列将被归纳地定义为阶段n = 0，1，2，..。. .阶段;舞台 通过归纳假设ui是pi对所有i n的prefix。 以来Ai<$Ai+1对于所有i，我们有闭包（ν（En（u0. un−1pn）= An.因此，在本发明中， ν你... un−1pn是[− 1，1]的一个整数。 通过归纳假设，我们知道F（u0. un−1）v0. vn−1B，因此，F（u0... un−1pn）∈v0. vn−1B. 设vn是N中最短的字符串，使得F（u0. un−1pn）∈ v0. vnB等thatforeachi ∈{0， .. . ，2n-1}，其中至少有一个j∈En（v0.. . vn）withCji，i+1 .这样的字符串vn存在，因为F（u0. n-1pn）必须是[-1，1]的一个抽象名称ular，contains [0， 1]. 此外，设un是pn的最短前缀，那么En（u0. un）包含所有数j< n，其中ν（j）∈An，且使得F（u0. unB）brief0. vnB. 这就结束了对阶段n的描述。很明显，以这种方式定义的序列具有上面提到的性质。现在我们定义r：= u0u1u2.. . .然后通过构造，闭包（ν（En（r）=（−∞，−1]<$[0，∞），因此<$ν（r）= [−1，0]。通过假设，F（r）是[-1，0]的一个非线性名称，因此，一个闭集A的非线性interior是（-1，0）的子集另一方面，通过F的连续性，我们有F（r）= v0v1v2.. . . 让我们固定一个任意点y∈[0，1]。序列v0v1v2... 列出半径任意小的有理立方体，任意接近y.因此，A必须包含任意接近y的点。因为A是封闭的，所以它也必须包含y。因为这对任意y∈[0， 1]都是真的，所以我们证明了[0， 1]<$A。正如上面所解释的，这是一个矛盾。(ii) 定理3.3的第二个断言的证明类似于第一个断言的证明在d= 1的情况下，人们可以用集合做类似的.ΣBn：=[−1，0]<$（0，1）<${ν（i）|i∈{0， . ， n−1} 随机数（ν）}。赫特林77⟨ ⟩∈⟨⟩∈⊆ → ⟨ ⟩∪∪<<<<<<<<<<<✷5并集和交集在这最后一节中，我们希望讨论四个“积极”的在第2节中介绍了θd、θd、θd、θd它们都来自于<<<<闭集和开集的基本表示ρ闭和ρ开。一可能会特别想知道，更奇特的表示θd和θd可能<<对...有好处它们的一个优点是它们允许有效的交集和并集计算。我们解释这个。给定两个序列p，qB，可以通过p，q：= p（0）q（0）p（1）q（1）..定义一个新的序列p，q B。. .如果γ是正则闭集的表示，那么[6]说并运算是（γ，γ，γ）-可计算的（（γ，γ，γ）-连续的），如果存在可计算的（连续的）函数F：B B，其中γ（F（p，q））= γ（p）γ（q）。类似于交集运算（我们只考虑正则闭集对的交集，其交集也是正则闭集）。第一个观察结果是，联合操作是 （d）<<<可计算的，但交集运算不是偶（d，d，d）<<<[6]。 对于下一个最简单的如果是另一种方式around：交集运算是（θ<$d，θ<$d，θ<$d）-可计算的，但并集运算是（θ <$d，θ<$d）-可计算的操作不是偶（θd，θd，θd）区间[0， 1]和[1， 2]，实现并集运算的连续函数关于，关于Rationald应该但永远不能枚举一个封闭的有理一个内部包含数字1的区间，内部的一个元素[0， 1][1， 2] = [0， 2]）。 但在ecan n节目中，交运算是（θd，θd，θd）-可计算的，也是（θ d，θ d，θ d）-可计算的<<<<<<可计算的;比较[9]并使用，除其他事项外，这一事实，即两个开放的稠密子集的交集的拓扑空间是稠密的再次（见引理12在附录[9]）。这给了我们一些考虑这两种稍微有点奇异的表示的动机另一个有趣的点是关于“积极的”表示法，这是令人惊讶的事实，由于齐格勒[8]，一个人可以减少一个“消极的它的代表性。这方面的在这篇文章中进行了更详细的分析，本文引用[1] 布拉特卡河谷和p.Hertling，实数表示的拓扑性质，理论计算机科学（即将出版）。[2] Brattka，V.和K. Weihrauch，Computability on subsets of Euclidean space I：Closed and compact subsets，Theoretical Computer Science219（1999），pp.65比93θθ赫特林78[3] Groé ts chel，M.，L. L ov'asz和A. 陈志荣，“几何算法与组合优化”，《算法与组合学》，北京，1988年。[4] Hertling，P.，一个有效的黎曼映射定理，理论计算机科学219（1999），pp。225-265[5] Weihrauch，K.，“Computability,” EATCS Monographs on Theoretical[6] Weihrauch，K.，“Computable Analysis,” Springer, Berlin,[7] Weihrauch，K.和C. Kreitz，Representations of the real numbers and of theopen subsets of the set of real numbers，Annals of Pure and Applied Logic35（1987），pp. 247-260[8] Ziegler，M.，欧几里得空间的正则子集的可计算性，数理逻辑季刊（即将出版）。[9]Ziegler，M.和v.Brattka，图灵（非）线性优化的可计算性，在：T. Biedl，编辑，第十三届加拿大计算几何会议（2001），pp.181